noip模拟59

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 100100;

#define int int64_t

template <typename LDXIN>
LDXIN read() {
  LDXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

class tree {
 private:
  int num;
  int ls[maxn*30], rs[maxn*30];

 public:
  int rt;
  int64_t sum[maxn*30], sz[maxn*30];
  void insert(int &x, int l, int r, int pos, int val) {
    if (!x) {
      x = ++num;
    }
    if (l == r) {
      sum[x] += 1ll * val * pos;
      sz[x] += val;
      return;
    }
    int mid = (l + r) / 2;
    if (mid <= 0 && l < 0) mid--;
    if (pos <= mid) {
      insert(ls[x], l, mid, pos, val);
    } else {
      insert(rs[x], mid + 1, r, pos, val);
    }
    sum[x] = sum[ls[x]] + sum[rs[x]];
    sz[x] = sz[ls[x]] + sz[rs[x]];
  }
  int query_sz(int x, int l, int r, int ql, int qr) {
    if (!x) return 0;
    if (ql <= l && r <= qr) {
      return sz[x];
    }
    int mid = (l + r) / 2;
    if (mid <= 0 && l < 0) mid--;
    int ans = 0;
    if (ql <= mid) {
      ans += query_sz(ls[x], l, mid, ql, qr);
    }
    if (qr > mid) {
      ans += query_sz(rs[x], mid + 1, r, ql, qr);
    }
    return ans;
  }
  int64_t query_sum(int x, int l, int r, int ql, int qr) {
    if (!x) return 0;
    if (ql <= l && r <= qr) {
      return sum[x];
    }
    int mid = (l + r) / 2;
    if (mid <= 0 && l < 0) mid--;
    int64_t ans = 0;
    if (ql <= mid) {
      ans += query_sum(ls[x], l, mid, ql, qr);
    }
    if (qr > mid) {
      ans += query_sum(rs[x], mid + 1, r, ql, qr);
    }
    return ans;
  }
} ltr, rtr;


int n;
int h[maxn];

int L = -1e5, R = 1e9 + 1e5;

int64_t getAns(int hh, int pos) {
  int64_t ans = 0;
  ans += 1ll * ltr.query_sz(ltr.rt, L, R, L, hh - pos - 1) * (hh - pos) -
         ltr.query_sum(ltr.rt, L, R, L, hh - pos - 1);
  ans += 1ll * rtr.query_sz(rtr.rt, L, R, L, hh + pos - 1) * (hh + pos) -
         rtr.query_sum(rtr.rt, L, R, L, hh + pos - 1);
  ans += ltr.query_sum(ltr.rt, L, R, hh - pos + 1, R) -
         1ll * ltr.query_sz(ltr.rt, L, R, hh - pos + 1, R) * (hh - pos);
  ans += rtr.query_sum(rtr.rt, L, R, hh + pos + 1, R) -
         1ll * rtr.query_sz(rtr.rt, L, R, hh + pos + 1, R) * (hh + pos);
  return ans;
}

int32_t main() {
  freopen("c.in", "r", stdin);
  freopen("c.out", "w", stdout);
  cin >> n;
  int mx = 0, mxid;
  For(i, 1, n) {
    cin >> h[i];
    if (h[i] > mx) {
      mx = h[i];
      mxid = i;
    }
    rtr.insert(rtr.rt, L, R, h[i] + i, 1);
  }
  int64_t ans = 0x3f3f3f3f3f3f3f3f;
  For(i, 1, n) {
    rtr.insert(rtr.rt, L, R, h[i] + i, -1);
    ltr.insert(ltr.rt, L, R, h[i] - i, 1);
    int l = max(i, n - i + 1), r = max(l, mx + abs(i - mxid));
    while (r - l > 1) {
      int mid = (l + r) / 2;
      int lwr = ltr.query_sz(ltr.rt, L, R, L, mid - i - 1) +
                rtr.query_sz(rtr.rt, L, R, L, mid + i - 1);
      int upr = n - lwr;
      if (upr >= lwr) {
        l = mid;
      } else {
        r = mid;
      }
    }
    ans = min(ans, min(getAns(l, i), getAns(r, i)));
  }
  cout << ans << endl;
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;

#define int int64_t

double l, c;
int32_t main() {
  freopen("a.in", "r", stdin);
  freopen("a.out", "w", stdout);
  int t;
  cin >> c >> t >> l;
  cout.flags(ios::fixed);
  cout.precision(c);
  For(i, 1, t) {
    int id;
    cin >> id;
    if (id == 1) {
      cout << 0 << ' ' << 0 << endl;
      continue;
    }
    if (id == 2) {
      cout << l << ' ' << l << endl;
      continue;
    }
    if (id == 3) {
      cout << 0 << ' ' << l << endl;
      continue;
    }
    if (id == 4) {
      cout << l << ' ' << 0 << endl;
      continue;
    }
    int lastno = log2(floor(sqrt(id - 1)) - 1);
    int remain;
    if (lastno == 0) {
      remain = id - 4;
    } else {
      remain = id - (pow(2, lastno) + 1) * (pow(2, lastno) + 1);
    }
    int sid = pow(4, lastno);
    int sLine = pow(2, lastno);
    int oLine = sLine + 1;
    // cout << sLine << endl;
    double dlt = l / sLine / 2;
    if (remain <= sid) {
      int cnt = 0;
      while (remain > sLine) {
        remain -= sLine;
        cnt++;
      }
      double x = dlt + dlt * cnt * 2;
      double y = dlt + (remain - 1) * dlt * 2;
      cout << x << ' ' << y << endl;
      continue;
    }

    remain -= sid;
    double x, y;
    int cnt = 0;
    while (remain) {
      if (cnt % 2) {
        if (remain <= oLine) break;

        remain -= oLine;
        cnt++;
        if (remain < sLine) break;
      } else {
        if (remain <= sLine) break;
        remain -= sLine;
        cnt++;
        if (remain < oLine) break;
      }
    }
    x = dlt * cnt;
    if (cnt % 2)
      y = (remain - 1) * dlt * 2;
    else
      y = remain * dlt * 2 - dlt;
    cout << x << ' ' << y << endl;
  }
  return 0;
}