# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
593899 |
2022-07-11T17:21:45 Z |
Do_you_copy |
Wall (IOI14_wall) |
C++17 |
|
1667 ms |
153864 KB |
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 2e6 + 1;
const int inf = 0x3f3f3f3f;
int n, k;
struct TNode{
int mmax, mmin, lazymax, lazymin;
TNode() : mmax(0), mmin(0), lazymax(-1), lazymin(inf){}
};
TNode st[maxN * 4];
void addmin(int id, int h){
if (st[id].lazymin < h) return;
st[id].lazymin = h;
st[id].lazymax = min(st[id].lazymax, h);
st[id].mmax = min(st[id].mmax, h);
st[id].mmin = min(st[id].mmin, h);
}
void addmax(int id, int h){
if (st[id].lazymax > h) return;
st[id].lazymax = h;
st[id].lazymin = max(st[id].lazymin, h);
st[id].mmax = max(st[id].mmax, h);
st[id].mmin = max(st[id].mmin, h);
}
void pull(int id){
addmax(id * 2, st[id].lazymax);
addmax(id * 2 + 1, st[id].lazymax);
addmin(id * 2, st[id].lazymin);
addmin(id * 2 + 1, st[id].lazymin);
st[id].lazymax = -1;
st[id].lazymin = inf;
}
void update(int id, int i, int j, int h, int t, int l = 0, int r = n - 1){
if (r < i || l > j) return;
if (i <= l && r <= j){
if (t) addmin(id, h);
else addmax(id, h);
return;
}
pull(id);
int mid = (l + r) / 2;
update(id * 2, i, j, h, t, l, mid);
update(id * 2 + 1, i, j, h, t, mid + 1, r);
st[id].mmax = max(st[id * 2].mmax, st[id * 2 + 1].mmax);
st[id].mmin = min(st[id * 2].mmin, st[id * 2 + 1].mmin);
}
int get(int id, int i, int l = 0, int r = n - 1){
if (l == r){
assert(st[id].mmax == st[id].mmin);
return st[id].mmax;
}
//if (i == 3) cerr << l << " " << r << " " << st[id].lazymax << ":\n";
pull(id);
int mid = (l + r) / 2;
if (mid >= i) return get(id * 2, i, l, mid);
else return get(id * 2 + 1, i, mid + 1, r);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N, k = K;
for (int i = 0; i < k; ++i){
update(1, left[i], right[i], height[i], op[i] - 1);
}
for (int i = 0; i < n; ++i){
finalHeight[i] = get(1, i);
}
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
125444 KB |
Output is correct |
2 |
Correct |
92 ms |
125672 KB |
Output is correct |
3 |
Correct |
63 ms |
125528 KB |
Output is correct |
4 |
Correct |
82 ms |
125772 KB |
Output is correct |
5 |
Correct |
81 ms |
125732 KB |
Output is correct |
6 |
Correct |
80 ms |
125696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
125528 KB |
Output is correct |
2 |
Correct |
236 ms |
135300 KB |
Output is correct |
3 |
Correct |
329 ms |
130768 KB |
Output is correct |
4 |
Correct |
811 ms |
136300 KB |
Output is correct |
5 |
Correct |
563 ms |
136780 KB |
Output is correct |
6 |
Correct |
495 ms |
137040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
125432 KB |
Output is correct |
2 |
Correct |
68 ms |
125552 KB |
Output is correct |
3 |
Correct |
75 ms |
125576 KB |
Output is correct |
4 |
Correct |
74 ms |
125756 KB |
Output is correct |
5 |
Correct |
64 ms |
125700 KB |
Output is correct |
6 |
Correct |
66 ms |
125772 KB |
Output is correct |
7 |
Correct |
59 ms |
125436 KB |
Output is correct |
8 |
Correct |
229 ms |
135224 KB |
Output is correct |
9 |
Correct |
349 ms |
130780 KB |
Output is correct |
10 |
Correct |
839 ms |
136264 KB |
Output is correct |
11 |
Correct |
519 ms |
136756 KB |
Output is correct |
12 |
Correct |
513 ms |
137044 KB |
Output is correct |
13 |
Correct |
59 ms |
125488 KB |
Output is correct |
14 |
Correct |
232 ms |
135292 KB |
Output is correct |
15 |
Correct |
132 ms |
126724 KB |
Output is correct |
16 |
Correct |
862 ms |
136556 KB |
Output is correct |
17 |
Correct |
493 ms |
136800 KB |
Output is correct |
18 |
Correct |
606 ms |
136732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
125412 KB |
Output is correct |
2 |
Correct |
72 ms |
125560 KB |
Output is correct |
3 |
Correct |
59 ms |
125480 KB |
Output is correct |
4 |
Correct |
71 ms |
125664 KB |
Output is correct |
5 |
Correct |
67 ms |
125740 KB |
Output is correct |
6 |
Correct |
84 ms |
125696 KB |
Output is correct |
7 |
Correct |
58 ms |
125508 KB |
Output is correct |
8 |
Correct |
316 ms |
135244 KB |
Output is correct |
9 |
Correct |
386 ms |
130772 KB |
Output is correct |
10 |
Correct |
885 ms |
136316 KB |
Output is correct |
11 |
Correct |
604 ms |
136732 KB |
Output is correct |
12 |
Correct |
575 ms |
137040 KB |
Output is correct |
13 |
Correct |
58 ms |
125504 KB |
Output is correct |
14 |
Correct |
238 ms |
135184 KB |
Output is correct |
15 |
Correct |
110 ms |
126620 KB |
Output is correct |
16 |
Correct |
1030 ms |
136548 KB |
Output is correct |
17 |
Correct |
520 ms |
136724 KB |
Output is correct |
18 |
Correct |
485 ms |
136724 KB |
Output is correct |
19 |
Correct |
1591 ms |
153864 KB |
Output is correct |
20 |
Correct |
1624 ms |
150472 KB |
Output is correct |
21 |
Correct |
1667 ms |
152948 KB |
Output is correct |
22 |
Correct |
1507 ms |
150520 KB |
Output is correct |
23 |
Correct |
1562 ms |
150504 KB |
Output is correct |
24 |
Correct |
1540 ms |
150548 KB |
Output is correct |
25 |
Correct |
1445 ms |
150496 KB |
Output is correct |
26 |
Correct |
1493 ms |
152976 KB |
Output is correct |
27 |
Correct |
1468 ms |
152972 KB |
Output is correct |
28 |
Correct |
1510 ms |
150448 KB |
Output is correct |
29 |
Correct |
1502 ms |
150496 KB |
Output is correct |
30 |
Correct |
1579 ms |
150468 KB |
Output is correct |