Submission #877241

#	Time	Username	Problem	Language	Result	Execution time	Memory
877241		GaLz	Wall (IOI14_wall)	C++14	100 / 100	740 ms	129484 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int maxn=2e6+5;
const int INF=1e9+5;
const ll mod=1e9+7;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define lb lower_bound
#define ub upper_bpund
#define fi first
#define se second
#define endl '\n'
struct Node {
    int max1, max2, min1, min2, lazy;
} seg[maxn*4];
int arr[maxn];
vi ans;
void merge(int now) {
    if(seg[now*2].max1==seg[now*2+1].max1) {
        seg[now].max1=seg[now*2].max1;
        seg[now].max2=max(seg[now*2].max2, seg[now*2+1].max2);
    } else {
        if(seg[now*2].max1>seg[now*2+1].max1) {
            seg[now].max1=seg[now*2].max1;
            seg[now].max2=max(seg[now*2].max2, seg[now*2+1].max1);
        } else {
            seg[now].max1=seg[now*2+1].max1;
            seg[now].max2=max(seg[now*2].max1, seg[now*2+1].max2);
        }
    }
    if(seg[now*2].min1==seg[now*2+1].min1) {
        seg[now].min1=seg[now*2].min1;
        seg[now].min2=min(seg[now*2].min2, seg[now*2+1].min2);
    } else {
        if(seg[now*2].min1<seg[now*2+1].min1) {
            seg[now].min1=seg[now*2].min1;
            seg[now].min2=min(seg[now*2].min2, seg[now*2+1].min1);
        } else {
            seg[now].min1=seg[now*2+1].min1;
            seg[now].min2=max(seg[now*2].min1, seg[now*2+1].min2);
        }
    }
}
// chmin update
void push_max(int now, int l, int r, int val) {
    if(val>=seg[now].max1) return;
    seg[now].max1=val;
    if(l==r) {
        seg[now].min1=seg[now].max1;
    } else {
        if(val<=seg[now].min1) {
            seg[now].min1=val;
        } else if(val<seg[now].min2) {
            seg[now].min2=val;
        }
    }
}
// chmax update
void push_min(int now, int l, int r, int val) {
    if(val<=seg[now].min1) return;
    seg[now].min1=val;
    if(l==r) {
        seg[now].max1=seg[now].min1;
    } else {
        if(val>=seg[now].max1) {
            seg[now].max1=val;
        } else if(val>seg[now].max2) {
            seg[now].max2=val;
        }
    }
}
void pushdown(int now, int l, int r) {
    if(l==r) return;
    int mid=(l+r)/2;
    push_max(now*2, l, mid, seg[now].max1);
    push_max(now*2+1, mid+1, r, seg[now].max1);
    push_min(now*2, l, mid, seg[now].min1);
    push_min(now*2+1, mid+1, r, seg[now].min1);
}
void build(int now, int l, int r) {
    if(l==r) {
        seg[now].max1=seg[now].min1=arr[l];
        seg[now].max2=-INF;
        seg[now].min2=INF;
    } else {
        int mid=(l+r)/2;
        build(now*2, l, mid);
        build(now*2+1, mid+1, r);
        merge(now);
    }
}
void update_chmin(int now, int l, int r, int posl, int posr, int val) {
    if(l>posr || r<posl || val>=seg[now].max1) return;
    if(l>=posl && r<=posr && val>seg[now].max2) {
        push_max(now, l, r, val);
        return;
    }
    pushdown(now, l, r);
    int mid=(l+r)/2;
    update_chmin(now*2, l, mid, posl, posr, val);
    update_chmin(now*2+1, mid+1, r, posl, posr, val);
    merge(now);
}
void update_chmax(int now, int l, int r, int posl, int posr, int val) {
    if(l>posr || r<posl || val<=seg[now].min1) return;
    if(l>=posl && r<=posr && val<seg[now].min2) {
        push_min(now, l, r, val);
        return;
    }
    pushdown(now, l, r);
    int mid=(l+r)/2;
    update_chmax(now*2, l, mid, posl, posr, val);
    update_chmax(now*2+1, mid+1, r, posl, posr, val);
    merge(now);
}
void query(int now, int l, int r) {
    if(l==r) {
        ans.pb(seg[now].max1);
        return;
    }
    pushdown(now, l, r);
    int mid=(l+r)/2;
    query(now*2, l, mid);
    query(now*2+1, mid+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    build(1, 1, n);
    for(int i=0; i<k; i++) {
        if(op[i]==1) {
            update_chmax(1, 1, n, left[i]+1, right[i]+1, height[i]);
        } else if(op[i]==2) {
            update_chmin(1, 1, n, left[i]+1, right[i]+1, height[i]);
        }
    }
    query(1, 1, n);
    for(int i=0; i<n; i++) finalHeight[i]=ans[i];
}

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