Submission #823932

#	Time	Username	Problem	Language	Result	Execution time	Memory
823932		annabeth9680	Wall (IOI14_wall)	C++17	0 / 100	2 ms	524 KiB

wall

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 8e6;
const int INF = 2000000011;
const pair<int,int> def = {-INF,INF};
pair<int,int> tree[MAXN]; //first is the add part, second remove
int ans[500005];
int N;
void build(int curl = 0, int curr = N-1, int p = 1){
    if(curl == 0 && curr == N-1){
        tree[p] = {0,0};
    }
    else{
        tree[p] = def;
    }
    int mid = (curl+curr)>>1;
    build(curl,mid,(p<<1)|1);
    build(mid+1,curr,(p<<1));
}
pair<int,int> comb(pair<int,int> a, pair<int,int> b){ //change b using a's info
    if(a.second < b.first){
        return {a.second,a.second};
    }
    if(a.first > b.second){
        return {a.first,a.first};
    }
    return {max(a.first,b.first),min(a.second,b.second)};
}
void push(int p){
    if(tree[p] != def){
        tree[(p<<1)] = comb(tree[p],tree[p<<1]);
        tree[(p<<1)|1] = comb(tree[p],tree[(p<<1)|1]);
        tree[p] = def;
    }
}
void update(int curl, int curr, int p, int findl, int findr, pair<int,int> val){
    if(findr < curl || curr < findl) return;
    if(findl < curl && curr < findr){
        tree[p] = comb(val,tree[p]);
        return;
    }
    if(curl != curr) push(p);
    int mid = (curl+curr)>>1;
    update(curl,mid,(p<<1),findl,findr,val);
    update(mid+1,curr,(p<<1)|1,findl,findr,val);
}
void query(int* ans, int p, int curl, int curr){
    if(curl == curr){
        ans[p] = tree[p].first;
        return;
    }
    push(p);
    int mid = (curl+curr)>>1;
    query(ans,p<<1,curl,mid);
    query(ans,(p<<1)|1,mid+1,curr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = n;
    build();
    for(int i = 0;i<k;++i){
        pair<int,int> val = def;
        if(op[i] == 1) val.first = height[i];
        else val.second = height[i];
        update(0,N-1,1,left[i],right[i],val);
    }
    query(ans,1,0,N-1);
}

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