Submission #717153

#	Time	Username	Problem	Language	Result	Execution time	Memory
717153		Urvuk3	Wall (IOI14_wall)	C++17	100 / 100	887 ms	99468 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)

vector<pii> seg;

pii Merge(pii p,pii q){
    if(p.fi<=q.fi && q.fi<=p.se) p.fi=q.fi;
    else if(q.fi>p.se){
        p.fi=q.fi;
        p.se=q.fi;
    }
    if(p.fi<=q.se && q.se<=p.se) p.se=q.se;
    else if(q.se<p.fi){
        p.fi=q.se;
        p.se=q.se;
    }
    return p;
}

void Propagate(int node,int l,int r){
    if(l!=r){
        seg[2*node]=Merge(seg[2*node],seg[node]);
        seg[2*node+1]=Merge(seg[2*node+1],seg[node]);
        seg[node]={0,INF};
    }
}

void UpdateR(int node,int l,int r,int L,int R,int x){
    Propagate(node,l,r);
    if(L<=l && r<=R){
        seg[node]=Merge(seg[node],{0,x});
        return;
    }
    if(L<=mid) UpdateR(2*node,l,mid,L,R,x);
    if(R>mid) UpdateR(2*node+1,mid+1,r,L,R,x);
}

void UpdateL(int node,int l,int r,int L,int R,int x){
    Propagate(node,l,r);
    if(L<=l && r<=R){
        seg[node]=Merge(seg[node],{x,INF});
        return;
    }
    if(L<=mid) UpdateL(2*node,l,mid,L,R,x);
    if(R>mid) UpdateL(2*node+1,mid+1,r,L,R,x);
}

pii Query(int node,int l,int r,int idx){
    if(l==r){
        return seg[node];
    }
    pii q;
    if(idx<=mid) q=Query(2*node,l,mid,idx);
    else q=Query(2*node+1,mid+1,r,idx);
    return Merge(q,seg[node]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    seg.resize(4*n+1,{0,INF});
    for(int i=0;i<k;i++){
        int tp=op[i];
        int l=left[i];
        int r=right[i];
        int x=height[i];
        if(tp==1) UpdateL(1,0,n-1,l,r,x);
        else UpdateR(1,0,n-1,l,r,x);
    }
    for(int i=0;i<n;i++){
        pii q=Query(1,0,n-1,i);
        finalHeight[i]=q.fi;
    }
    return;
}

/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

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