Submission #973982

#	Time	Username	Problem	Language	Result	Execution time	Memory
973982		Kavelmydex	Wall (IOI14_wall)	C++17	0 / 100	5 ms	33372 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;
pi t[4*N];
int lazy[4*N];

void prop(int x,int l,int r){
    if(lazy[x] == -1) return;
    t[x].f = t[x].s = lazy[x];
    if(l != r){
        lazy[lc] = lazy[x];
        lazy[rc] = lazy[x];
    }
    lazy[x] = -1;
}   
pi fun(pi x,pi y){
    pi ret;
    ret.f = min(x.f,y.f);
    ret.s = max(x.s,y.s);
    return ret;
}
pi calc(int L,int R, int x=1,int l=1,int r=n){
    if(R < l || r < L) return {OO,-OO};
    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].f >= v) return;
    if(L <= l && r <= R && t[x].s < v){
        lazy[x] = 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].s <= v) return;
    if(L <= l && r <= R && t[x].f > v){
        lazy[x] = 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[]){
    memset(lazy,-1,sizeof(lazy));
    For(i,k){
        left[i]++, right[i]++;
        if(op[i] == 1){
            upd_add(left[i],right[i],height[i]);
        }else{
            upd_remove(left[i],right[i],height[i]);
        }
    }
    rep(i,1,n+1){
        finalHeight[i-1] = calc(i,i).f;
    }
    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; 
//     while(k--){
//         cin >> tp >> l >> r >> h;
//         l++, r++;
//         if(tp == 1){
//             upd_add(l,r,h);
//         }else{
//             upd_remove(l,r,h);
//         }
//     }
//     rep(i,1,n+1){
//         cout << calc(i,i).f << 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: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39