# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
391521 |
2021-04-19T07:26:28 Z |
Aldas25 |
Wall (IOI14_wall) |
C++14 |
|
1010 ms |
102416 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAXN = 2000100;
const int INF = 1e9;
int tree[2][4*MAXN], lazy[2][4*MAXN];
int n;
void build (int id = 1, int le = 0, int ri = n-1) {
if (le == ri) {
tree[0][id] = lazy[0][id] = -1e9;
tree[1][id] = lazy[1][id] = 1e9;
return;
}
int mid = (le+ri)/2;
build (2*id, le, mid);
build (2*id+1, mid+1, ri);
tree[0][id] = lazy[0][id] = -INF;
tree[1][id] = lazy[1][id] = INF;
}
void shift (int id) {
int a = lazy[0][id], b = lazy[1][id];
if (a == -INF && b == INF) return;
FOR(ch, 2*id, 2*id+1) {
/* cout << "------ shifted a = " << a << " b = " << b << " id = " << id << " to ch = " << ch << endl;
cout << " tree[0] = " << tree[0][ch] << " tree[1] = " << tree[1][ch] << endl;
cout << " lazy[0] = " << lazy[0][ch] << " lazy[1] = " << lazy[1][ch] << endl; */
tree[0][ch] = max(a, tree[0][ch]);
tree[1][ch] = max(a, tree[1][ch]);
tree[1][ch] = min(b, tree[1][ch]);
tree[0][ch] = min(tree[0][ch], tree[1][ch]);
lazy[0][ch] = max(a, lazy[0][ch]);
lazy[1][ch] = max(a, lazy[1][ch]);
lazy[1][ch] = min(b, lazy[1][ch]);
lazy[0][ch] = min(lazy[0][ch], lazy[1][ch]);
/* cout << " tree[0] = " << tree[0][ch] << " tree[1] = " << tree[1][ch] << endl;
cout << " lazy[0] = " << lazy[0][ch] << " lazy[1] = " << lazy[1][ch] << endl; */
}
lazy[0][id] = -INF;
lazy[1][id] = INF;
}
int get (int p, int id = 1, int le = 0, int ri = n-1) {
if (le == ri) {
int x = 0;
x = max(x, tree[0][id]);
x = min(x, tree[1][id]);
return x;
}
shift (id);
int mid = (le+ri)/2;
if (p <= mid)
return get(p, 2*id, le, mid);
else
return get(p, 2*id+1, mid+1, ri);
}
void upd (int op, int x, int y, int h, int id = 1, int le = 0, int ri = n-1) {
if (x > ri || y < le) return;
if (x <= le && ri <= y) {
if (op == 1) {
tree[0][id] = max(tree[0][id], h);
tree[1][id] = max(tree[1][id], h);
lazy[0][id] = max(lazy[0][id], h);
lazy[1][id] = max(lazy[1][id], h);
lazy[0][id] = min(lazy[0][id], lazy[1][id]);
tree[0][id] = min(tree[0][id], tree[1][id]);
} else {
tree[0][id] = min(tree[0][id], h);
tree[1][id] = min(tree[1][id], h);
lazy[0][id] = min(lazy[0][id], h);
lazy[1][id] = min(lazy[1][id], h);
lazy[0][id] = min(lazy[0][id], lazy[1][id]);
tree[0][id] = min(tree[0][id], tree[1][id]);
}
/* cout << "--- id = " << id << " le = " << le << " ri = " << ri << endl;
cout << " tree[0] = " << tree[0][id] << " tree[1] = " << tree[1][id] << endl;
cout << " lazy[0] = " << lazy[0][id] << " lazy[1] = " << lazy[1][id] << endl; */
return;
}
shift (id);
int mid = (le+ri)/2;
upd (op, x, y, h, 2*id, le, mid);
upd (op, x, y, h, 2*id+1, mid+1, ri);
}
void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int ans[]){
//FOR(i, 0, n-1) ans[i] = height[i];
n = _n;
build ();
FOR(i, 0, k-1) {
upd (op[i], left[i], right[i], height[i]);
/* cout << " after op i=" << i << ": ";
FOR(j, 0, n-1) cout << get(j) << " ";
cout << endl; */
}
FOR(i, 0, n-1) ans[i] = get(i);
return;
}
/*
###
in:
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
ans:
0
0
0
39412
39412
39412
48623
48623
48623
48623
###
in:
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
ans:
3
4
5
4
3
3
0
0
1
0
10 4
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
8 ms |
1100 KB |
Output is correct |
5 |
Correct |
6 ms |
1076 KB |
Output is correct |
6 |
Correct |
7 ms |
1100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
159 ms |
9796 KB |
Output is correct |
3 |
Correct |
213 ms |
6252 KB |
Output is correct |
4 |
Correct |
649 ms |
14408 KB |
Output is correct |
5 |
Correct |
317 ms |
23504 KB |
Output is correct |
6 |
Correct |
310 ms |
22024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
320 KB |
Output is correct |
4 |
Correct |
8 ms |
1100 KB |
Output is correct |
5 |
Correct |
8 ms |
1100 KB |
Output is correct |
6 |
Correct |
7 ms |
1088 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
161 ms |
9732 KB |
Output is correct |
9 |
Correct |
224 ms |
6468 KB |
Output is correct |
10 |
Correct |
635 ms |
14392 KB |
Output is correct |
11 |
Correct |
313 ms |
23480 KB |
Output is correct |
12 |
Correct |
309 ms |
21896 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
161 ms |
13908 KB |
Output is correct |
15 |
Correct |
36 ms |
2540 KB |
Output is correct |
16 |
Correct |
682 ms |
22684 KB |
Output is correct |
17 |
Correct |
340 ms |
22084 KB |
Output is correct |
18 |
Correct |
350 ms |
22084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
460 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
8 ms |
1092 KB |
Output is correct |
5 |
Correct |
6 ms |
1040 KB |
Output is correct |
6 |
Correct |
6 ms |
1100 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
161 ms |
9760 KB |
Output is correct |
9 |
Correct |
218 ms |
6340 KB |
Output is correct |
10 |
Correct |
650 ms |
14440 KB |
Output is correct |
11 |
Correct |
323 ms |
23528 KB |
Output is correct |
12 |
Correct |
337 ms |
21924 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
160 ms |
13892 KB |
Output is correct |
15 |
Correct |
36 ms |
2500 KB |
Output is correct |
16 |
Correct |
661 ms |
22668 KB |
Output is correct |
17 |
Correct |
310 ms |
22232 KB |
Output is correct |
18 |
Correct |
347 ms |
22056 KB |
Output is correct |
19 |
Correct |
1006 ms |
102356 KB |
Output is correct |
20 |
Correct |
995 ms |
99884 KB |
Output is correct |
21 |
Correct |
992 ms |
102316 KB |
Output is correct |
22 |
Correct |
983 ms |
99876 KB |
Output is correct |
23 |
Correct |
982 ms |
99784 KB |
Output is correct |
24 |
Correct |
966 ms |
99964 KB |
Output is correct |
25 |
Correct |
968 ms |
99884 KB |
Output is correct |
26 |
Correct |
976 ms |
102416 KB |
Output is correct |
27 |
Correct |
966 ms |
102364 KB |
Output is correct |
28 |
Correct |
1010 ms |
99792 KB |
Output is correct |
29 |
Correct |
975 ms |
99928 KB |
Output is correct |
30 |
Correct |
975 ms |
99868 KB |
Output is correct |