Submission #1276339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276339		quanduongxuan12	Wall (IOI14_wall)	C++20	24 / 100	480 ms	16588 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define name "wall"
#define MAXN 2000006
#define pb push_back
#define pf push_front
#define ll long long
#define ii pair<int, int>
#define fs first
#define sc second
#define ill pair<int, ll>
#define lli pair<ll, int>
#define llll pair<ll, ll>
#define all(v) v.begin(),v.end()
#define uni(v) v.erase(unique(all(v)),v.end())
#define bit(n,i) (((n)>>(i))&1)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define MASK(i) (1LL<<(i))
const int INF=1e9;
const int MOD=1e9+7;
void add(int &u, int v){
    u+=v;
    if (u>=MOD) u-=MOD;
}
void sub(int &u, int v){
    u-=v;
    if (u<0) u+=MOD;
}
bool minimize(int &u, int v){
    if (u>v){
        u=v;
        return 1;
    }
    return 0;
}
bool maximize(int &u, int v){
    if (u<v){
        u=v;
        return 1;
    }
    return 0;
}
long long Rand(long long l, long long r){
    ll tmp=0;
    FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand()));
    return l+tmp%(r-l+1);
}
int st[4*MAXN];
ii lazy[2][4*MAXN];
void down(int id, int l, int r, bool type){
    if (l==r) return;
    if ((type==0&&lazy[type][id].fs==0)||(type==1&&lazy[type][id].fs==INF)) return;
    if (type==0){
        maximize(st[id<<1],lazy[type][id].fs);
        maximize(st[id<<1|1],lazy[type][id].fs);
        if (maximize(lazy[type][id<<1].fs,lazy[type][id].fs)){
            lazy[type][id<<1].sc=lazy[type][id].sc;
        }
        if (maximize(lazy[type][id<<1|1].fs,lazy[type][id].fs)){
            lazy[type][id<<1|1].sc=lazy[type][id].sc;
        }
        lazy[type][id]={0,0};
    }
    else{
        minimize(st[id<<1],lazy[type][id].fs);
        minimize(st[id<<1|1],lazy[type][id].fs);
        if (minimize(lazy[type][id<<1].fs,lazy[type][id].fs)){
            lazy[type][id<<1].sc=lazy[type][id].sc;
        }
        if (minimize(lazy[type][id<<1|1].fs,lazy[type][id].fs)){
            lazy[type][id<<1|1].sc=lazy[type][id].sc;
        }
        lazy[type][id]={INF,0};
    }
}
void update(int id, int l, int r, int u, int v, int val, bool type, int times){
    if (l>v||r<u) return;
    if (l>=u&&r<=v){
        if (type==0){
            maximize(st[id],val);
            if (maximize(lazy[type][id].fs,val)){
                lazy[type][id].sc=times;
            }
        }
        else{
            minimize(st[id],val);
            if (minimize(lazy[type][id].fs,val)){
                lazy[type][id].sc=times;
            }
        }
        down(id,l,r,type^1);
        down(id,l,r,type);
        return;
    }
    down(id,l,r,type^1);
    down(id,l,r,type);
    int mid=(l+r)/2;
    update(id<<1,l,mid,u,v,val,type,times);
    update(id<<1|1,mid+1,r,u,v,val,type,times);
}
void get(int id, int l, int r, int res[]){
    if (l==r){
        res[l-1]=st[id];
        return;
    }
    if (lazy[0][id].sc<lazy[1][id].sc){
        down(id,l,r,0);
        down(id,l,r,1);
    }
    else{
        down(id,l,r,1);
        down(id,l,r,0);
    }
    int mid=(l+r)/2;
    get(id<<1,l,mid,res);
    get(id<<1|1,mid+1,r,res);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int finalHeight[]){
    FOR(i,1,4*n){
        lazy[0][i]={0,0};
        lazy[1][i]={INF,0};
    }
    FORD(i,q,1){
        op[i]=op[i-1]-1;
        l[i]=l[i-1]+1;
        r[i]=r[i-1]+1;
        h[i]=h[i-1];
    }
    FOR(i,1,q){
        int type=op[i],u=l[i],v=r[i],val=h[i];
        update(1,1,n,u,v,val,type,i);
    }
    get(1,1,n,finalHeight);
}

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