| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 961953 |
2024-04-12T20:00:15 Z |
ttamx |
Wall (IOI14_wall) |
C++17 |
|
609 ms |
86064 KB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int K=1<<22;
const int INF=INT_MAX/2;
struct segtree{
int t[K],mn[K],mx[K];
void apply(int i,int mnn,int mxx){
t[i]=max(min(t[i],mnn),mxx);
mn[i]=max(min(mn[i],mnn),mxx);
mx[i]=max(min(mx[i],mnn),mxx);
}
void push(int i){
apply(i*2,mn[i],mx[i]);
apply(i*2+1,mn[i],mx[i]);
mn[i]=INF;
mx[i]=-INF;
}
void build(int l,int r,int i){
mn[i]=INF,mx[i]=-INF;
if(l==r)return;
int m=(l+r)/2;
build(l,m,i*2);
build(m+1,r,i*2+1);
}
void update(int l,int r,int i,int x,int y,int mnn,int mxx){
if(y<l||r<x)return;
if(x<=l&&r<=y)return apply(i,mnn,mxx);
int m=(l+r)/2;
push(i);
update(l,m,i*2,x,y,mnn,mxx);
update(m+1,r,i*2+1,x,y,mnn,mxx);
}
void answer(int l,int r,int i,int a[]){
if(l==r)return void(a[l]=t[i]);
int m=(l+r)/2;
push(i);
answer(l,m,i*2,a);
answer(m+1,r,i*2+1,a);
}
}s;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
s.build(0,n-1,1);
for(int i=0;i<k;i++)s.update(0,n-1,1,left[i],right[i],op[i]==2?height[i]:INF,op[i]==1?height[i]:-INF);
s.answer(0,n-1,1,finalHeight);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4804 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4852 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
112 ms |
18012 KB |
Output is correct |
| 3 |
Correct |
132 ms |
14752 KB |
Output is correct |
| 4 |
Correct |
384 ms |
27548 KB |
Output is correct |
| 5 |
Correct |
253 ms |
28672 KB |
Output is correct |
| 6 |
Correct |
233 ms |
27124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4600 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
114 ms |
18000 KB |
Output is correct |
| 9 |
Correct |
138 ms |
15984 KB |
Output is correct |
| 10 |
Correct |
398 ms |
27620 KB |
Output is correct |
| 11 |
Correct |
240 ms |
28572 KB |
Output is correct |
| 12 |
Correct |
241 ms |
26964 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
112 ms |
18188 KB |
Output is correct |
| 15 |
Correct |
22 ms |
10076 KB |
Output is correct |
| 16 |
Correct |
386 ms |
27984 KB |
Output is correct |
| 17 |
Correct |
239 ms |
27276 KB |
Output is correct |
| 18 |
Correct |
236 ms |
27304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4672 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4700 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4700 KB |
Output is correct |
| 6 |
Correct |
4 ms |
4956 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
113 ms |
17960 KB |
Output is correct |
| 9 |
Correct |
137 ms |
15992 KB |
Output is correct |
| 10 |
Correct |
405 ms |
27620 KB |
Output is correct |
| 11 |
Correct |
235 ms |
28672 KB |
Output is correct |
| 12 |
Correct |
236 ms |
27204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 14 |
Correct |
119 ms |
17944 KB |
Output is correct |
| 15 |
Correct |
23 ms |
9968 KB |
Output is correct |
| 16 |
Correct |
400 ms |
28144 KB |
Output is correct |
| 17 |
Correct |
250 ms |
27304 KB |
Output is correct |
| 18 |
Correct |
240 ms |
27460 KB |
Output is correct |
| 19 |
Correct |
593 ms |
85892 KB |
Output is correct |
| 20 |
Correct |
562 ms |
83524 KB |
Output is correct |
| 21 |
Correct |
578 ms |
85904 KB |
Output is correct |
| 22 |
Correct |
570 ms |
83540 KB |
Output is correct |
| 23 |
Correct |
576 ms |
83528 KB |
Output is correct |
| 24 |
Correct |
558 ms |
83476 KB |
Output is correct |
| 25 |
Correct |
558 ms |
83524 KB |
Output is correct |
| 26 |
Correct |
609 ms |
85868 KB |
Output is correct |
| 27 |
Correct |
569 ms |
86064 KB |
Output is correct |
| 28 |
Correct |
563 ms |
83460 KB |
Output is correct |
| 29 |
Correct |
569 ms |
83600 KB |
Output is correct |
| 30 |
Correct |
551 ms |
83536 KB |
Output is correct |
