| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 113976 |
2019-05-29T12:13:59 Z |
E869120 |
Wall (IOI14_wall) |
C++14 |
|
2347 ms |
174740 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
class RangeMin {
public:
vector<int>dat; int size_ = 1;
void init(int sz, int t) {
while (size_ <= sz) size_ *= 2;
dat.resize(size_ * 2, t);
}
void update(int pos, int x) {
pos += size_;
dat[pos] = x;
while (pos >= 2) {
pos >>= 1;
dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
}
}
int query_(int l, int r, int a, int b, int u) {
//cout << l << " " << r << " " << a << " " << b << " " << u << " " << dat.size() << endl;
if (l <= a) return dat[u];
if (b <= l) return (1 << 30);
int v1 = query_(l, r, a, (a + b) >> 1, u * 2);
int v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return min(v1, v2);
}
int query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
int N, Q, ty[1 << 21], L[1 << 21], R[1 << 21], H[1 << 21];
RangeMin AL, AR;
vector<int> E[1 << 21][2];
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N = n; Q = k;
for (int i = 1; i <= Q; i++) { ty[i] = op[i - 1]; L[i] = left[i - 1]; R[i] = right[i - 1]; H[i] = height[i - 1]; }
AL.init(Q + 2, 0);
AR.init(Q + 2, 1000000);
for (int i = 1; i <= Q; i++) { E[L[i]][0].push_back(i); E[R[i]][1].push_back(i); }
for (int i = 0; i < N; i++) {
for (int pos : E[i][0]) { if (ty[pos] == 1) AL.update(pos, -H[pos]); if (ty[pos] == 2) AR.update(pos, H[pos]); }
int G = AL.size_, S = 0;
for (int i = (G >> 1); i >= 1; i >>= 1) {
int SS = S + i;
int P1 = -AL.query(SS, G);
int P2 = AR.query(SS, G);
if (P1 > P2) { S += i; }
}
if (S == 0) {
finalHeight[i] = -AL.query(0, G);
}
else {
int V1 = -AL.query(S, G);
int V2 = AR.query(S, G);
if (V1 == H[S]) finalHeight[i] = V2;
else finalHeight[i] = V1;
}
for (int pos : E[i][1]) { if (ty[pos] == 1) AL.update(pos, 0); if (ty[pos] == 2) AR.update(pos, 1000000); }
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
98808 KB |
Output is correct |
| 2 |
Correct |
89 ms |
99292 KB |
Output is correct |
| 3 |
Correct |
96 ms |
98936 KB |
Output is correct |
| 4 |
Correct |
105 ms |
99448 KB |
Output is correct |
| 5 |
Correct |
95 ms |
99492 KB |
Output is correct |
| 6 |
Correct |
94 ms |
99516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
98780 KB |
Output is correct |
| 2 |
Correct |
285 ms |
126960 KB |
Output is correct |
| 3 |
Correct |
250 ms |
113016 KB |
Output is correct |
| 4 |
Correct |
788 ms |
132856 KB |
Output is correct |
| 5 |
Correct |
396 ms |
131176 KB |
Output is correct |
| 6 |
Correct |
387 ms |
131032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
98868 KB |
Output is correct |
| 2 |
Correct |
96 ms |
99288 KB |
Output is correct |
| 3 |
Correct |
90 ms |
98936 KB |
Output is correct |
| 4 |
Correct |
96 ms |
99492 KB |
Output is correct |
| 5 |
Correct |
98 ms |
99364 KB |
Output is correct |
| 6 |
Correct |
95 ms |
99400 KB |
Output is correct |
| 7 |
Correct |
84 ms |
98808 KB |
Output is correct |
| 8 |
Correct |
284 ms |
126888 KB |
Output is correct |
| 9 |
Correct |
251 ms |
112888 KB |
Output is correct |
| 10 |
Correct |
771 ms |
132920 KB |
Output is correct |
| 11 |
Correct |
410 ms |
131192 KB |
Output is correct |
| 12 |
Correct |
390 ms |
130944 KB |
Output is correct |
| 13 |
Correct |
84 ms |
98808 KB |
Output is correct |
| 14 |
Correct |
284 ms |
126940 KB |
Output is correct |
| 15 |
Correct |
116 ms |
101368 KB |
Output is correct |
| 16 |
Correct |
836 ms |
132956 KB |
Output is correct |
| 17 |
Correct |
401 ms |
130552 KB |
Output is correct |
| 18 |
Correct |
398 ms |
130260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
98796 KB |
Output is correct |
| 2 |
Correct |
93 ms |
99192 KB |
Output is correct |
| 3 |
Correct |
88 ms |
99036 KB |
Output is correct |
| 4 |
Correct |
97 ms |
99448 KB |
Output is correct |
| 5 |
Correct |
98 ms |
99444 KB |
Output is correct |
| 6 |
Correct |
95 ms |
99448 KB |
Output is correct |
| 7 |
Correct |
85 ms |
98808 KB |
Output is correct |
| 8 |
Correct |
427 ms |
126940 KB |
Output is correct |
| 9 |
Correct |
275 ms |
112928 KB |
Output is correct |
| 10 |
Correct |
794 ms |
132904 KB |
Output is correct |
| 11 |
Correct |
422 ms |
131192 KB |
Output is correct |
| 12 |
Correct |
398 ms |
130812 KB |
Output is correct |
| 13 |
Correct |
88 ms |
98876 KB |
Output is correct |
| 14 |
Correct |
295 ms |
126952 KB |
Output is correct |
| 15 |
Correct |
127 ms |
101340 KB |
Output is correct |
| 16 |
Correct |
906 ms |
133164 KB |
Output is correct |
| 17 |
Correct |
415 ms |
130692 KB |
Output is correct |
| 18 |
Correct |
412 ms |
130248 KB |
Output is correct |
| 19 |
Correct |
2302 ms |
164316 KB |
Output is correct |
| 20 |
Correct |
2266 ms |
172244 KB |
Output is correct |
| 21 |
Correct |
2306 ms |
174688 KB |
Output is correct |
| 22 |
Correct |
2247 ms |
172236 KB |
Output is correct |
| 23 |
Correct |
2246 ms |
172172 KB |
Output is correct |
| 24 |
Correct |
2309 ms |
172304 KB |
Output is correct |
| 25 |
Correct |
2329 ms |
172408 KB |
Output is correct |
| 26 |
Correct |
2337 ms |
174624 KB |
Output is correct |
| 27 |
Correct |
2347 ms |
174740 KB |
Output is correct |
| 28 |
Correct |
2251 ms |
172220 KB |
Output is correct |
| 29 |
Correct |
2231 ms |
172288 KB |
Output is correct |
| 30 |
Correct |
2285 ms |
172352 KB |
Output is correct |
