# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
203075 |
2020-02-19T08:23:58 Z |
detaomega |
Wall (IOI14_wall) |
C++14 |
|
1037 ms |
117036 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define de(x,y) cout<<#x<<" :"<<x<<y;
//#define int long long
#define SZ(xx) ((int)xx.size())
#define lowbit(xx) (xx&(-xx))
#define pb push_back
#define ls node*2
#define rs node*2+1
typedef pair<int,int> pii;
const int maxn = 3e6+5;
const int INF = 1e9+5;
int mx[maxn * 4], mn[maxn * 4], tag[maxn * 4], ans[maxn];
void ppush(int node) {
mx[ls] = max(mx[ls], mx[node]);
mx[rs] = max(mx[rs], mx[node]);
mn[ls] = min(mn[ls], mn[node]);
mn[rs] = min(mn[rs], mn[node]);
}
void push(int node) {
if(mn[ls] != INF) {
ppush(ls);
mx[ls] = min(mx[ls], mn[ls]);
}
if(mn[rs] != INF) {
ppush(rs);
mx[rs] = min(mx[rs], mn[rs]);
}
if(tag[node]) {
tag[rs] = tag[ls] = 1;
mn[rs] = mn[ls] = INF;
}
mx[ls] = max(mx[ls], mx[node]);
mx[rs] = max(mx[rs], mx[node]);
mn[ls] = min(mn[ls], mn[node]);
mn[rs] = min(mn[rs], mn[node]);
mx[node] = 0;
mn[node] = INF;
tag[node] = 0;
}
void upd(int node,int l,int r,int a,int b,int type,int val) {
if(l != r)push(node);
if(a <= l && r <= b) {
if(type == 1) {
if(mn[node] != INF)
mx[node] = min(mn[node], mx[node]);
tag[node] = 1;
mn[node] = INF;
mx[node] = max(mx[node], val);
}
else {
tag[node] = 0;
mn[node] = min(mn[node], val);
mx[node] = min(mx[node], mn[node]);
}
}
else {
int m = (l + r) >> 1;
if(a <= m) upd(ls, l, m, a, b, type, val);
if(b > m) upd(rs, m+1, r, a, b, type, val);
}
}
void travel(int node,int l,int r) {
if(l == r) {
if(mn[node] != INF)
ans[l] = min(mn[node], mx[node]);
else
ans[l] = mx[node];
}
else {
push(node);
int m = (l + r) >> 1;
travel(ls, l, m);
travel(rs, m+1, r);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=1; i<=n * 2+10; i++) {
mx[i] = 0;
mn[i] = INF;
tag[i] = 1;
}
for(int i=0; i<k; i++) {
upd(1, 1, n, left[i]+1, right[i]+1, op[i], height[i]);
}
travel(1, 1, n);
for(int j=1; j<=n; j++) {
finalHeight[j-1] = ans[j];
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
508 KB |
Output is correct |
3 |
Correct |
7 ms |
376 KB |
Output is correct |
4 |
Correct |
13 ms |
1272 KB |
Output is correct |
5 |
Correct |
11 ms |
1276 KB |
Output is correct |
6 |
Correct |
11 ms |
1404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
184 ms |
9080 KB |
Output is correct |
3 |
Correct |
209 ms |
6008 KB |
Output is correct |
4 |
Correct |
816 ms |
15352 KB |
Output is correct |
5 |
Correct |
354 ms |
14840 KB |
Output is correct |
6 |
Correct |
319 ms |
14844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
504 KB |
Output is correct |
3 |
Correct |
6 ms |
376 KB |
Output is correct |
4 |
Correct |
13 ms |
1276 KB |
Output is correct |
5 |
Correct |
11 ms |
1276 KB |
Output is correct |
6 |
Correct |
11 ms |
1272 KB |
Output is correct |
7 |
Correct |
4 ms |
380 KB |
Output is correct |
8 |
Correct |
184 ms |
8824 KB |
Output is correct |
9 |
Correct |
203 ms |
5752 KB |
Output is correct |
10 |
Correct |
836 ms |
14968 KB |
Output is correct |
11 |
Correct |
326 ms |
14456 KB |
Output is correct |
12 |
Correct |
339 ms |
14456 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
182 ms |
8824 KB |
Output is correct |
15 |
Correct |
45 ms |
2936 KB |
Output is correct |
16 |
Correct |
769 ms |
15328 KB |
Output is correct |
17 |
Correct |
327 ms |
15352 KB |
Output is correct |
18 |
Correct |
338 ms |
15224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
7 ms |
480 KB |
Output is correct |
3 |
Correct |
6 ms |
380 KB |
Output is correct |
4 |
Correct |
13 ms |
1272 KB |
Output is correct |
5 |
Correct |
11 ms |
1272 KB |
Output is correct |
6 |
Correct |
11 ms |
1272 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
184 ms |
8800 KB |
Output is correct |
9 |
Correct |
214 ms |
5792 KB |
Output is correct |
10 |
Correct |
783 ms |
14944 KB |
Output is correct |
11 |
Correct |
330 ms |
14456 KB |
Output is correct |
12 |
Correct |
322 ms |
14456 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
181 ms |
8824 KB |
Output is correct |
15 |
Correct |
47 ms |
2904 KB |
Output is correct |
16 |
Correct |
814 ms |
15172 KB |
Output is correct |
17 |
Correct |
331 ms |
15224 KB |
Output is correct |
18 |
Correct |
336 ms |
15208 KB |
Output is correct |
19 |
Correct |
985 ms |
116852 KB |
Output is correct |
20 |
Correct |
956 ms |
114424 KB |
Output is correct |
21 |
Correct |
968 ms |
117036 KB |
Output is correct |
22 |
Correct |
968 ms |
114548 KB |
Output is correct |
23 |
Correct |
962 ms |
114552 KB |
Output is correct |
24 |
Correct |
964 ms |
114424 KB |
Output is correct |
25 |
Correct |
978 ms |
114544 KB |
Output is correct |
26 |
Correct |
989 ms |
116856 KB |
Output is correct |
27 |
Correct |
987 ms |
116584 KB |
Output is correct |
28 |
Correct |
1037 ms |
114180 KB |
Output is correct |
29 |
Correct |
990 ms |
114040 KB |
Output is correct |
30 |
Correct |
958 ms |
114040 KB |
Output is correct |