Submission #973999

#	Time	Username	Problem	Language	Result	Execution time	Memory
973999		Kavelmydex	Wall (IOI14_wall)	C++17	100 / 100	1181 ms	120532 KiB

wall

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pi pair<int,int>
#define vi vector<int>
#define rep(i,x,n) for(int i=x; i<n; ++i)
#define For(i,n) rep(i,0,n)
#define endl "\n"
#define sp ' '
#define pb push_back
#define f first
#define s second
#define sz size()
#define all(x) (x).begin(),(x).end()
 
#define lc ((x<<1))
#define rc ((x<<1)|1)
#define mid ((l+r)>>1)
 
const int N = 2e6+1, OO = 1e9, mod = 1e9+7, mx = 5e5+1;
const int dx[]{0,0,1,-1}, dy[]{1,-1,0,0};
void tr(int a, int b){cout << a << sp << b << endl;}
void cmx(int &a, int b){a = max(a,b);}
void cmn(int &a, int b){a = min(a,b);}
 
int n;
struct node {
    int mx,mn,lazy=-1;
};
node t[4*N];
 
void prop(int x,int l,int r){
    if(t[x].lazy == -1) return;
    t[x].mn = t[x].mx = t[x].lazy;
    if(l != r){
        t[lc].lazy = t[x].lazy;
        t[rc].lazy = t[x].lazy;
    }
    t[x].lazy = -1;
}   
node fun(node x,node y){
    node ret;
    ret.mn = min(x.mn,y.mn);
    ret.mx = max(x.mx,y.mx);
    return ret;
}
node calc(int L,int R, int x=1,int l=1,int r=n){
    if(R < l || r < L) return {-OO,OO,-1};
    prop(x,l,r);
    if(L <= l && r <= R) return t[x];
    return fun(calc(L,R,lc,l,mid),calc(L,R,rc,mid+1,r));
} 
void upd_add(int L, int R, int v, int x=1, int l=1, int r=n){
    prop(x,l,r);
    if(r < L || R < l || t[x].mn >= v) return;
    if(L <= l && r <= R && t[x].mx < v){
        t[x].lazy = v;        
        prop(x,l,r);    
        return;     
    }
    upd_add(L,R,v,lc,l,mid);
    upd_add(L,R,v,rc,mid+1,r);
    t[x] = fun(t[lc],t[rc]);
}
void upd_remove(int L, int R, int v, int x=1, int l=1, int r=n){
    prop(x,l,r);
    if(r < L || R < l || t[x].mx <= v) return;
    if(L <= l && r <= R && t[x].mn > v){
        t[x].lazy = v;       
        prop(x,l,r);    
        return;     
    }
    upd_remove(L,R,v,lc,l,mid);
    upd_remove(L,R,v,rc,mid+1,r);
    t[x] = fun(t[lc],t[rc]);
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    For(i,k){
        left[i]++, right[i]++;
        if(op[i] == 1){
            upd_add(left[i],right[i],height[i],1,1,n);
        }else{
            upd_remove(left[i],right[i],height[i],1,1,n);
        }
    }
    rep(i,1,n+1){
        finalHeight[i-1] = calc(i,i,1,1,n).mn;
    }
    return;
}
 
// int32_t main() {
//     ios::sync_with_stdio(0); cin.tie(0); 
//     // freopen("talent.in", "r", stdin);
//     // freopen("talent.out", "w", stdout);   
//     memset(lazy,-1,sizeof(lazy));
//     int k; cin >> n >> k;
//     int tp,l,r,h; 
//     int op[k],left[k],right[k],height[k],finalHeight[n];
//     For(i,k){
//         cin >> op[i] >> left[i] >> right[i] >> height[i];
//     }
//     buildWall(n,k,op,left,right,height,finalHeight);
//     For(i,n) cout << finalHeight[i] << sp;
//     cout << endl;
//     return 0;   
// }
/*
Just some notices : 
I believe you can do it !
You've done things that were harder ... 
Stay calm and focused  =)
*/

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39