# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
94718 |
2019-01-23T09:28:16 Z |
someone_aa |
Wall (IOI14_wall) |
C++17 |
|
1328 ms |
86052 KB |
#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 2000100;
const int inf = 1e9;
int n, q;
struct interval {
public:
int l, r;
bool mark;
};
interval tree[4*maxn];
interval un(interval a, interval b) {
interval c = {min(a.l, b.l), max(a.r, b.r)};
return c;
}
interval in(interval a, interval b) {
interval c;
if(a.r < b.l) c = {b.l, b.l};
else if(a.l > b.r) c = {b.r, b.r};
else c = {max(a.l, b.l), min(a.r, b.r)};
return c;
}
interval mergef(interval a, interval b) {
return un(a, b);
}
void set_update(interval val, int li, int ri, int index) {
tree[index] = in(tree[index], val);
if(li != ri) {
tree[index].mark = true;
}
}
void push_update(int li, int ri, int index) {
if(tree[index].mark) {
int mid = (li+ri)/2;
set_update(tree[index], li, mid, 2*index);
set_update(tree[index], mid+1, ri, 2*index+1);
tree[index].mark = false;
}
}
void update(int ul, int ur, interval val, int li=0, int ri=n-1, int index=1) {
//cout<<li<<" "<<ri<<" -> "<<tree[index].l<<" "<<tree[index].r<<"\n";
if(li > ur || ri < ul) return;
else if(li >= ul && ri <= ur) {
//cout<<"Updating range: ["<<li<<", "<<ri<<"] -> "<<val.l<<" "<<val.r<<"\n";
set_update(val, li, ri, index);
}
else {
int mid = (li+ri)/2;
push_update(li, ri, index);
update(ul,ur,val,li,mid,2*index);
update(ul,ur,val,mid+1,ri,2*index+1);
tree[index] = un(tree[2*index], tree[2*index+1]);
}
}
interval query(int ul, int ur, int li=0, int ri=n-1, int index=1) {
push_update(li, ri, index);
if(li > ur || ri < ul) return {inf, -inf};
else if(li >= ul && ri <= ur) {
return tree[index];
}
else {
int mid = (li+ri)/2;
interval left_q = {inf, -inf};
interval right_q = {inf, -inf};
if(ul <= mid) left_q = query(ul, ur, li, mid, 2*index);
else right_q = query(ul, ur, mid+1, ri, 2*index+1);
tree[index] = un(tree[2*index], tree[2*index+1]);
if(ul <= mid) return left_q;
else return right_q;
}
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
int q = 0;
while(q < k) {
int q_type = op[q];
int x = height[q];
int l = left[q];
int r = right[q];
if(q_type == 1) {
interval up = {x, inf};
update(l, r, up);
}
else {
interval up = {-inf, x};
update(l, r, up);
}
q++;
}
for(int i=0;i<n;i++) {
finalHeight[i] = query(i,i).l;
}
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
380 KB |
Output is correct |
4 |
Correct |
10 ms |
1016 KB |
Output is correct |
5 |
Correct |
8 ms |
1016 KB |
Output is correct |
6 |
Correct |
9 ms |
1016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
175 ms |
13952 KB |
Output is correct |
3 |
Correct |
218 ms |
8312 KB |
Output is correct |
4 |
Correct |
677 ms |
21496 KB |
Output is correct |
5 |
Correct |
335 ms |
22552 KB |
Output is correct |
6 |
Correct |
321 ms |
20984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
11 ms |
1016 KB |
Output is correct |
5 |
Correct |
8 ms |
1048 KB |
Output is correct |
6 |
Correct |
9 ms |
1016 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
148 ms |
13988 KB |
Output is correct |
9 |
Correct |
219 ms |
8316 KB |
Output is correct |
10 |
Correct |
672 ms |
21544 KB |
Output is correct |
11 |
Correct |
334 ms |
22660 KB |
Output is correct |
12 |
Correct |
315 ms |
20956 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
153 ms |
14056 KB |
Output is correct |
15 |
Correct |
44 ms |
2424 KB |
Output is correct |
16 |
Correct |
786 ms |
21724 KB |
Output is correct |
17 |
Correct |
333 ms |
21112 KB |
Output is correct |
18 |
Correct |
344 ms |
21240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
10 ms |
1016 KB |
Output is correct |
5 |
Correct |
9 ms |
1016 KB |
Output is correct |
6 |
Correct |
9 ms |
1016 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
150 ms |
13988 KB |
Output is correct |
9 |
Correct |
220 ms |
8392 KB |
Output is correct |
10 |
Correct |
698 ms |
21552 KB |
Output is correct |
11 |
Correct |
331 ms |
22520 KB |
Output is correct |
12 |
Correct |
321 ms |
21144 KB |
Output is correct |
13 |
Correct |
2 ms |
256 KB |
Output is correct |
14 |
Correct |
152 ms |
14020 KB |
Output is correct |
15 |
Correct |
44 ms |
2296 KB |
Output is correct |
16 |
Correct |
758 ms |
21752 KB |
Output is correct |
17 |
Correct |
333 ms |
21240 KB |
Output is correct |
18 |
Correct |
336 ms |
21308 KB |
Output is correct |
19 |
Correct |
1319 ms |
85880 KB |
Output is correct |
20 |
Correct |
1307 ms |
83448 KB |
Output is correct |
21 |
Correct |
1319 ms |
85864 KB |
Output is correct |
22 |
Correct |
1326 ms |
83512 KB |
Output is correct |
23 |
Correct |
1301 ms |
83356 KB |
Output is correct |
24 |
Correct |
1291 ms |
83364 KB |
Output is correct |
25 |
Correct |
1281 ms |
83436 KB |
Output is correct |
26 |
Correct |
1311 ms |
86052 KB |
Output is correct |
27 |
Correct |
1292 ms |
85700 KB |
Output is correct |
28 |
Correct |
1290 ms |
83448 KB |
Output is correct |
29 |
Correct |
1305 ms |
83476 KB |
Output is correct |
30 |
Correct |
1328 ms |
83308 KB |
Output is correct |