Submission #823969

#	Time	Username	Problem	Language	Result	Execution time	Memory
823969		annabeth9680	Wall (IOI14_wall)	C++17	0 / 100	121 ms	262144 KiB

wall

#include <bits/stdc++.h>
using namespace std;
const int INF = 2000000011;
const pair<int,int> def = make_pair(-INF,INF);
pair<int,int> tree[8000000]; //first is the add part, second remove
int N, Q; 
void build(int curl = 0, int curr = N-1, int p = 1){
    if(curl == 0 && curr == N-1){
        tree[p] = make_pair(0,0); 
    }
    else{
        tree[p] = def;
    }
  	if(curl == curr) return; 
    int mid = (curl+curr)>>1;
    build(curl,mid,p<<1);
    build(mid+1,curr,p<<1|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 make_pair(a.second,a.second);
    }
    if(a.first > b.second){
        return make_pair(a.first,a.first);
    }
    return make_pair(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* lb, int* rb, int* h, int* ans){
    N = n; Q = k; 
    build();
    for(int q = 0;q<Q;++q){
        pair<int,int> val = def;
        if(op[q] == 1) val.first = h[q];
        else val.second = h[q];
        update(0,N-1,1,lb[q],rb[q],val);
    }
    query(ans,1,0,N-1);
}
int n, q,op[500005], lb[500005], rb[500005], h[500005], ans[500005];

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