Submission #991067

#	Time	Username	Problem	Language	Result	Execution time	Memory
991067		gggkik	Wall (IOI14_wall)	C++14	100 / 100	639 ms	112904 KiB

wall

#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 (stderr)

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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39