oj.uz

Submission #991067

# Submission time Handle Problem Language Result Execution time Memory
991067 2024-06-01T08:16:03 Z gggkik Wall (IOI14_wall) C++14
100 / 100
 639 ms 112904 KB 
#include <wall.h>
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e6+5;
int t[MXN*4], lo[MXN*4], hi[MXN*4];
const int inf = 1e9;
void push(int x,int s,int e){
    if(s!=e){
        if(lo[x]!=-1e9) { 
            lo[x*2] = max(lo[x*2],lo[x]);
            hi[x*2] = max(hi[x*2],lo[x]);
            lo[x*2+1] = max(lo[x*2+1],lo[x]);
            hi[x*2+1] = max(hi[x*2+1],lo[x]);
        }
        if(hi[x]!=1e9){
            lo[x*2] = min(lo[x*2],hi[x]);
            hi[x*2] = min(hi[x*2],hi[x]);
            lo[x*2+1] = min(lo[x*2+1],hi[x]);
            hi[x*2+1] = min(hi[x*2+1],hi[x]);
        }
    }
    else {
        t[x] = max(t[x],lo[x]);
        t[x] = min(t[x],hi[x]);
    }
    lo[x] = -1e9;
    hi[x] = 1e9;
}
void upd(int x,int s,int e,int l,int r,int v,int t){
    push(x,s,e);
    if(e<l || r<s) return;
    if(l<=s && e<=r) {
        if(t==1) lo[x] = v;
        else hi[x] = v;
        
        return push(x,s,e);
    }
    int mid = s+e>>1;
    upd(x*2,s,mid,l,r,v,t), upd(x*2+1,mid+1,e,l,r,v,t);
}
int get(int x,int s,int e,int p){
    push(x,s,e);
    if(s==e) return x;
    int mid = s+e>>1;
    if(p<=mid) return get(x*2,s,mid,p);
    return get(x*2+1,mid+1,e,p);
}
void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 1;i<=4*n;i++) lo[i] = -1e9, hi[i] = 1e9;
    upd(1,0,n-1,0,n-1,0,1);
    upd(1,0,n-1,0,n-1,0,2);
    for(int i = 0;i<q;i++){
        int t,l,r,v;
      	t = op[i];
      	l = left[i];
      	r = right[i];
      	v = height[i];
        upd(1,0,n-1,l,r,v,t);
    }
    for(int i = 0;i<n;i++){
        int x = get(1,0,n-1,i); 
        finalHeight[i] = t[x];
    }
}

Compilation message

wall.cpp: In function 'void upd(int, int, int, int, int, int, int)':
wall.cpp:38:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = s+e>>1;
      |               ~^~
wall.cpp: In function 'int get(int, int, int, int)':
wall.cpp:44:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = s+e>>1;
      |               ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2552 KB Output is correct
4 Correct 5 ms 2908 KB Output is correct
5 Correct 4 ms 2908 KB Output is correct
6 Correct 4 ms 2908 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 85 ms 16100 KB Output is correct
3 Correct 133 ms 10612 KB Output is correct
4 Correct 357 ms 23376 KB Output is correct
5 Correct 198 ms 24656 KB Output is correct
6 Correct 186 ms 22868 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2504 KB Output is correct
4 Correct 5 ms 2904 KB Output is correct
5 Correct 4 ms 2952 KB Output is correct
6 Correct 4 ms 2908 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 84 ms 15904 KB Output is correct
9 Correct 127 ms 12048 KB Output is correct
10 Correct 361 ms 23312 KB Output is correct
11 Correct 188 ms 24400 KB Output is correct
12 Correct 183 ms 22864 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 85 ms 16104 KB Output is correct
15 Correct 35 ms 5976 KB Output is correct
16 Correct 445 ms 23680 KB Output is correct
17 Correct 194 ms 23124 KB Output is correct
18 Correct 201 ms 23376 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 2948 KB Output is correct
5 Correct 4 ms 2908 KB Output is correct
6 Correct 4 ms 2948 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 85 ms 16068 KB Output is correct
9 Correct 131 ms 11856 KB Output is correct
10 Correct 366 ms 23380 KB Output is correct
11 Correct 208 ms 24404 KB Output is correct
12 Correct 181 ms 22868 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 89 ms 16104 KB Output is correct
15 Correct 25 ms 5996 KB Output is correct
16 Correct 440 ms 23708 KB Output is correct
17 Correct 192 ms 23120 KB Output is correct
18 Correct 189 ms 23196 KB Output is correct
19 Correct 604 ms 112724 KB Output is correct
20 Correct 583 ms 110416 KB Output is correct
21 Correct 581 ms 112724 KB Output is correct
22 Correct 615 ms 110380 KB Output is correct
23 Correct 549 ms 110196 KB Output is correct
24 Correct 569 ms 110416 KB Output is correct
25 Correct 594 ms 110256 KB Output is correct
26 Correct 639 ms 112904 KB Output is correct
27 Correct 586 ms 112892 KB Output is correct
28 Correct 591 ms 110324 KB Output is correct
29 Correct 565 ms 110256 KB Output is correct
30 Correct 578 ms 110416 KB Output is correct