| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 254058 |
2020-07-29T09:37:33 Z |
b00n0rp |
Wall (IOI14_wall) |
C++17 |
|
1066 ms |
107260 KB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pii pair<int,int>
#define F first
#define S second
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
const int MX = 2000005;
const int INF = 100000000;
struct node{
int vadd,vsub;
node(){
vadd = -INF;
vsub = INF;
}
};
node seg[4*MX];
int ans[MX];
void change(int ind,int type,int val){
if(type == 1){
remax(seg[ind].vadd,val);
remax(seg[ind].vsub,val);
}
else remin(seg[ind].vsub,val);
}
void push(int ind,int l,int r){
if(l == r) return;
change(2*ind,1,seg[ind].vadd);
change(2*ind,2,seg[ind].vsub);
change(2*ind+1,1,seg[ind].vadd);
change(2*ind+1,2,seg[ind].vsub);
seg[ind].vadd = -INF;
seg[ind].vsub = INF;
}
void upd(int ind, int l, int r, int x, int y, int type,int val){
push(ind,l,r);
if(l > y or r < x) return;
if(l >= x and r <= y){
change(ind,type,val);
push(ind,l,r);
return;
}
int m = (l+r)/2;
upd(2*ind,l,m,x,y,type,val);
upd(2*ind+1,m+1,r,x,y,type,val);
}
void calc(int ind,int l,int r){
push(ind,l,r);
if(l == r){
ans[l] = min(seg[ind].vadd,seg[ind].vsub);
return;
}
int m = (l+r)/2;
calc(2*ind,l,m);
calc(2*ind+1,m+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
upd(1,0,n-1,0,n-1,1,0);
upd(1,0,n-1,0,n-1,2,0);
REP(i,k) upd(1,0,n-1,left[i],right[i],op[i],height[i]);
calc(1,0,n-1);
REP(i,n) finalHeight[i] = ans[i];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
62968 KB |
Output is correct |
| 2 |
Correct |
35 ms |
63100 KB |
Output is correct |
| 3 |
Correct |
34 ms |
62968 KB |
Output is correct |
| 4 |
Correct |
39 ms |
63352 KB |
Output is correct |
| 5 |
Correct |
39 ms |
63228 KB |
Output is correct |
| 6 |
Correct |
38 ms |
63224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
62976 KB |
Output is correct |
| 2 |
Correct |
211 ms |
76664 KB |
Output is correct |
| 3 |
Correct |
255 ms |
70360 KB |
Output is correct |
| 4 |
Correct |
654 ms |
81400 KB |
Output is correct |
| 5 |
Correct |
415 ms |
82424 KB |
Output is correct |
| 6 |
Correct |
411 ms |
81020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
62976 KB |
Output is correct |
| 2 |
Correct |
36 ms |
63096 KB |
Output is correct |
| 3 |
Correct |
40 ms |
62968 KB |
Output is correct |
| 4 |
Correct |
44 ms |
63224 KB |
Output is correct |
| 5 |
Correct |
43 ms |
63224 KB |
Output is correct |
| 6 |
Correct |
39 ms |
63224 KB |
Output is correct |
| 7 |
Correct |
34 ms |
62976 KB |
Output is correct |
| 8 |
Correct |
209 ms |
76536 KB |
Output is correct |
| 9 |
Correct |
264 ms |
70136 KB |
Output is correct |
| 10 |
Correct |
612 ms |
81400 KB |
Output is correct |
| 11 |
Correct |
415 ms |
82424 KB |
Output is correct |
| 12 |
Correct |
418 ms |
80888 KB |
Output is correct |
| 13 |
Correct |
33 ms |
62976 KB |
Output is correct |
| 14 |
Correct |
209 ms |
76792 KB |
Output is correct |
| 15 |
Correct |
66 ms |
64248 KB |
Output is correct |
| 16 |
Correct |
621 ms |
81884 KB |
Output is correct |
| 17 |
Correct |
413 ms |
81152 KB |
Output is correct |
| 18 |
Correct |
414 ms |
81084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
62968 KB |
Output is correct |
| 2 |
Correct |
39 ms |
63104 KB |
Output is correct |
| 3 |
Correct |
41 ms |
62968 KB |
Output is correct |
| 4 |
Correct |
43 ms |
63228 KB |
Output is correct |
| 5 |
Correct |
45 ms |
63224 KB |
Output is correct |
| 6 |
Correct |
39 ms |
63232 KB |
Output is correct |
| 7 |
Correct |
38 ms |
62968 KB |
Output is correct |
| 8 |
Correct |
216 ms |
76536 KB |
Output is correct |
| 9 |
Correct |
260 ms |
70228 KB |
Output is correct |
| 10 |
Correct |
647 ms |
81436 KB |
Output is correct |
| 11 |
Correct |
419 ms |
82424 KB |
Output is correct |
| 12 |
Correct |
410 ms |
80844 KB |
Output is correct |
| 13 |
Correct |
33 ms |
62968 KB |
Output is correct |
| 14 |
Correct |
205 ms |
76536 KB |
Output is correct |
| 15 |
Correct |
75 ms |
64376 KB |
Output is correct |
| 16 |
Correct |
618 ms |
81656 KB |
Output is correct |
| 17 |
Correct |
409 ms |
81016 KB |
Output is correct |
| 18 |
Correct |
397 ms |
81016 KB |
Output is correct |
| 19 |
Correct |
906 ms |
107260 KB |
Output is correct |
| 20 |
Correct |
887 ms |
104824 KB |
Output is correct |
| 21 |
Correct |
913 ms |
107216 KB |
Output is correct |
| 22 |
Correct |
913 ms |
104696 KB |
Output is correct |
| 23 |
Correct |
909 ms |
104696 KB |
Output is correct |
| 24 |
Correct |
910 ms |
104696 KB |
Output is correct |
| 25 |
Correct |
922 ms |
104696 KB |
Output is correct |
| 26 |
Correct |
910 ms |
107208 KB |
Output is correct |
| 27 |
Correct |
935 ms |
107180 KB |
Output is correct |
| 28 |
Correct |
1066 ms |
104696 KB |
Output is correct |
| 29 |
Correct |
926 ms |
104696 KB |
Output is correct |
| 30 |
Correct |
931 ms |
104696 KB |
Output is correct |
