Submission #247632

#	Time	Username	Problem	Language	Result	Execution time	Memory
247632		LittleFlowers__	Wall (IOI14_wall)	C++17	100 / 100	767 ms	69624 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define gg exit(0);

#include "wall.h"

const int INF=1e9,
          N=2000010;

int add[N*4],rev[N*4];

void Add(int &i,int &j,int t){
    if(j<=t){
        i=j=t;
        //i=t;
        //j=INF;
    } else{
        i=max(i,t);
    }
}
void Rev(int &i,int &j,int t){
    j=min(j,t);
}

void join(int i,int j){
    Add(add[i],rev[i],add[j]);
    Rev(add[i],rev[i],rev[j]);
}

void upd(int s,int l,int r,int u,int v,int op,int h){
    if(l>v||u>r) return;
    if(u<=l&&r<=v){
        if(op==1){
            Add(add[s],rev[s],h);
        } else{
            Rev(add[s],rev[s],h);
        }
        return;
    }
    join(2*s,s); join(2*s+1,s);
    add[s]=-INF;
    rev[s]=INF;
    int m=(l+r)/2;
    upd(2*s,l,m,u,v,op,h); upd(2*s+1,m+1,r,u,v,op,h);
}
void build(int s,int l,int r){
    add[s]=0; rev[s]=INF;
    if(l==r){
        return;
    }
    int m=(l+r)/2;
    build(2*s,l,m); build(2*s+1,m+1,r);
}
void get(int s,int l,int r,int ans[]){
    if(l==r){
        ans[l]=min(add[s],rev[s]);
        return;
    }
    int m=(l+r)/2;
    join(2*s,s); join(2*s+1,s);
    get(2*s,l,m,ans); get(2*s+1,m+1,r,ans);
}

void buildWall(int n,int k,int op[],int l[],int r[],int h[],int ans[]){
    forinc(i,0,k-1){
        upd(1,0,n-1,l[i],r[i],op[i],h[i]);
    }
    /**

    //cerr<<add[1]<<" "<<rev[1];
    //cout<<add[3]<<" "<<rev[3];
    join(3,1);
    //Add(add[3],rev[3],1);
    //+ -INF -1

    +2 -INF
    +1 -INF

    +6 -4 +4

    +2 -4 + 4

    >= - INF <=1 +1
        = 1
    //cout<<add[3]<<" "<<rev[3];
    //gg
    //join(6,3);
    //cout<<add[6]<<" "<<rev[6];
    gg
    join(1,3);
    gg
    */
    get(1,0,n-1,ans);
}

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