Submission #549017

#	Time	Username	Problem	Language	Result	Execution time	Memory
549017		enerelt14	Wall (IOI14_wall)	C++14	100 / 100	828 ms	138472 KiB

wall

#include<bits/stdc++.h>
using namespace std;
int n, q;
struct node{
    int lazy, mn, mx;
    node(){
        lazy=-1;
        mn=0;
        mx=0;
    }
};
node tree[8000005];
int res[2000005], num=0;
void propagate(int id, int l, int r){
    if (l==r)return;
    if (tree[id].lazy!=-1){
        tree[id*2+1].lazy=tree[id].lazy;
        tree[id*2+2].lazy=tree[id].lazy;
        tree[id*2+1].mn=tree[id].lazy;
        tree[id*2+1].mx=tree[id].lazy;
        tree[id*2+2].mn=tree[id].lazy;
        tree[id*2+2].mx=tree[id].lazy;
    }
    tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
    tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
    tree[id].lazy=-1;
}
void update1(int id, int l, int r, int L, int R, int h){
    if (L>r || l>R || tree[id].mn>=h)return;
    if (L<=l && r<=R && tree[id].mn==tree[id].mx){
        tree[id].lazy=max(tree[id].lazy, h);
        tree[id].mn=max(tree[id].mn, h);
        tree[id].mx=max(tree[id].mx, h);
        //cout<<id<<" "<<l<<" "<<r<<" "<<tree[id].lazy<<" "<<tree[id].mn<<" "<<tree[id].mx<<"\n";
        return;
    }
    propagate(id, l, r);
    int m=(l+r)/2;
    update1(id*2+1, l, m, L, R, h);
    update1(id*2+2, m+1, r, L, R, h);
    tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
    tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
}
void update2(int id, int l, int r, int L, int R, int h){
    if (L>r || l>R || tree[id].mx<=h)return;
    if (L<=l && r<=R && tree[id].mn==tree[id].mx){
        if (tree[id].lazy!=-1)tree[id].lazy=min(tree[id].lazy, h);
        else tree[id].lazy=h;
        tree[id].mn=min(tree[id].mn, h);
        tree[id].mx=min(tree[id].mx, h);
        //cout<<id<<" "<<l<<" "<<r<<" "<<tree[id].lazy<<" "<<tree[id].mn<<" "<<tree[id].mx<<"\n";
        return;
    }
    propagate(id, l, r);
    int m=(l+r)/2;
    update2(id*2+1, l, m, L, R, h);
    update2(id*2+2, m+1, r, L, R, h);
    tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
    tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
}
void solve(int id, int l, int r){
    propagate(id, l, r);
    if (l==r){
        res[num]=tree[id].mn;
        num++;
        return;
    }
    int m=(l+r)/2;
    solve(id*2+1, l, m);
    solve(id*2+2, m+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i=0;i<k;i++){
        if (op[i]==1)update1(0, 0, n-1, left[i], right[i], height[i]);
        else update2(0, 0, n-1, left[i], right[i], height[i]);
    }
    solve(0, 0, n-1);
    for (int i=0;i<n;i++)finalHeight[i]=res[i];
    return;
}

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