| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 92511 |
2019-01-03T08:21:10 Z |
easrui |
벽 (IOI14_wall) |
C++14 |
|
649 ms |
77304 KB |
#include <bits/stdc++.h>
#define vl first
#define vr second
//#include "wall.h"
using namespace std;
typedef pair<int,int> pii;
const int MN = 2e6+5;
pii ST[4*MN];
int finH[MN];
void init(int s, int e, int pos)
{
ST[pos].vl = 0;
ST[pos].vr = MN;
if(s==e) return;
int m = (s+e)/2;
init(s,m,2*pos);
init(m+1,e,2*pos+1);
}
void fin(int s, int e, int pos)
{
int L = ST[pos].vl, R = ST[pos].vr;
if(s==e){
finH[s] = L;
return;
}
int m = (s+e)/2;
ST[2*pos].vl = max(ST[2*pos].vl,L);
ST[2*pos].vr = max(ST[2*pos].vr,L);
ST[2*pos].vl = min(ST[2*pos].vl,R);
ST[2*pos].vr = min(ST[2*pos].vr,R);
ST[2*pos+1].vl = max(ST[2*pos+1].vl,L);
ST[2*pos+1].vr = max(ST[2*pos+1].vr,L);
ST[2*pos+1].vl = min(ST[2*pos+1].vl,R);
ST[2*pos+1].vr = min(ST[2*pos+1].vr,R);
fin(s, m, 2*pos);
fin(m+1, e, 2*pos+1);
}
void upt(int qu, int l, int r, int h, int s, int e, int pos)
{
if(e<l || s>r) return;
int L = ST[pos].vl, R = ST[pos].vr;
if(l<=s && e<=r){
if(qu==1){
ST[pos].vl = max(L,h);
ST[pos].vr = max(R,h);
}
else{
ST[pos].vl = min(L,h);
ST[pos].vr = min(R,h);
}
return ;
}
int m = (s+e)/2;
ST[2*pos].vl = max(ST[2*pos].vl,L);
ST[2*pos].vr = max(ST[2*pos].vr,L);
ST[2*pos].vl = min(ST[2*pos].vl,R);
ST[2*pos].vr = min(ST[2*pos].vr,R);
ST[2*pos+1].vl = max(ST[2*pos+1].vl,L);
ST[2*pos+1].vr = max(ST[2*pos+1].vr,L);
ST[2*pos+1].vl = min(ST[2*pos+1].vl,R);
ST[2*pos+1].vr = min(ST[2*pos+1].vr,R);
ST[pos].vl = 0;
ST[pos].vr = MN;
upt(qu, l, r, h, s, m, 2*pos);
upt(qu, l, r, h, m+1, e, 2*pos+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
init(0,n-1,1);
//cout << height[0] << '\n';
for(int i=0; i<k; i++) upt(op[i],left[i],right[i],height[i],0,n-1,1);
//cout << 1 << '\n';
fin(0,n-1,1);
for(int i=0; i<n; i++) finalHeight[i] = finH[i];
};
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
7 ms |
888 KB |
Output is correct |
| 5 |
Correct |
6 ms |
888 KB |
Output is correct |
| 6 |
Correct |
6 ms |
888 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
148 ms |
14060 KB |
Output is correct |
| 3 |
Correct |
161 ms |
8184 KB |
Output is correct |
| 4 |
Correct |
466 ms |
20872 KB |
Output is correct |
| 5 |
Correct |
286 ms |
22048 KB |
Output is correct |
| 6 |
Correct |
278 ms |
20316 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
7 ms |
892 KB |
Output is correct |
| 5 |
Correct |
6 ms |
888 KB |
Output is correct |
| 6 |
Correct |
6 ms |
888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
147 ms |
14172 KB |
Output is correct |
| 9 |
Correct |
160 ms |
8056 KB |
Output is correct |
| 10 |
Correct |
457 ms |
20952 KB |
Output is correct |
| 11 |
Correct |
285 ms |
21972 KB |
Output is correct |
| 12 |
Correct |
278 ms |
20336 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
149 ms |
14024 KB |
Output is correct |
| 15 |
Correct |
27 ms |
2296 KB |
Output is correct |
| 16 |
Correct |
472 ms |
21112 KB |
Output is correct |
| 17 |
Correct |
279 ms |
20572 KB |
Output is correct |
| 18 |
Correct |
281 ms |
20472 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
508 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
7 ms |
888 KB |
Output is correct |
| 5 |
Correct |
6 ms |
888 KB |
Output is correct |
| 6 |
Correct |
6 ms |
888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
380 KB |
Output is correct |
| 8 |
Correct |
147 ms |
14072 KB |
Output is correct |
| 9 |
Correct |
164 ms |
8060 KB |
Output is correct |
| 10 |
Correct |
465 ms |
20904 KB |
Output is correct |
| 11 |
Correct |
282 ms |
22152 KB |
Output is correct |
| 12 |
Correct |
270 ms |
20344 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
148 ms |
14072 KB |
Output is correct |
| 15 |
Correct |
27 ms |
2168 KB |
Output is correct |
| 16 |
Correct |
446 ms |
21212 KB |
Output is correct |
| 17 |
Correct |
281 ms |
20492 KB |
Output is correct |
| 18 |
Correct |
280 ms |
20472 KB |
Output is correct |
| 19 |
Correct |
639 ms |
77304 KB |
Output is correct |
| 20 |
Correct |
634 ms |
74960 KB |
Output is correct |
| 21 |
Correct |
649 ms |
77300 KB |
Output is correct |
| 22 |
Correct |
633 ms |
74872 KB |
Output is correct |
| 23 |
Correct |
632 ms |
74744 KB |
Output is correct |
| 24 |
Correct |
632 ms |
74872 KB |
Output is correct |
| 25 |
Correct |
634 ms |
74904 KB |
Output is correct |
| 26 |
Correct |
632 ms |
77200 KB |
Output is correct |
| 27 |
Correct |
640 ms |
77112 KB |
Output is correct |
| 28 |
Correct |
620 ms |
74744 KB |
Output is correct |
| 29 |
Correct |
638 ms |
74740 KB |
Output is correct |
| 30 |
Correct |
622 ms |
74768 KB |
Output is correct |
