Submission #711363

#	Time	Username	Problem	Language	Result	Execution time	Memory
711363		Pherokung	Wall (IOI14_wall)	C++14	0 / 100	432 ms	21752 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
#define MAXK 500005
#define F first
#define S second
#define INF 1000000007
using namespace std;
typedef pair<pair<int,int>,int> pa;
int n,k,op[MAXK],l[MAXK],r[MAXK],h[MAXK];
pa v;
struct node{
    int val;
    pa lazy;
    node *l, *r;
};
node top;

void build(node *pos,int be,int ed){
    if(be == ed){
        pos->val = 0;
        pos->lazy = {{0,0},0};
        return;
    }
    pos->l = new node, pos->r = new node;
    int mid = (be+ed) / 2;
    build(pos->l,be,mid), build(pos->r,mid+1,ed);
    pos->lazy = {{0,0},0};
}

int hi(int a,int o){
    if(a) return h[a];
    else{
        if(o == 1) return -INF;
        else if(o == 2)return INF;
        else return 0;
    }
}

pa merge(pa A,pa B){ // A = OLD, B = NEW
    //printf("(%d %d %d) , (%d %d %d)",A.F.F,A.F.S,A.S,B.F.F,B.F.S,B.S);
    pa C;
    if(B.S) C = B;
    else if(hi(A.F.F,1) >= hi(B.F.F,1) && hi(A.F.S,2) <= hi(B.F.S,2)) C = A;
    else if(hi(A.F.F,1) <= hi(B.F.F,1) && hi(A.F.S,2) >= hi(B.F.S,2)) C = B;
    else if(hi(A.F.F,1) > hi(B.F.F,1)){
        C = {{A.F.F, B.F.S}, A.S};
        if(hi(C.F.F,1) > hi(C.F.S,2)){
            C = {{0,0},B.F.S};
            if(B.F.F > B.F.S) C.F.F = B.F.F;
        }
    }
    else if(hi(A.F.S,2) < hi(B.F.S,2)){
        C = {{B.F.F, A.F.S}, A.S};
        if(hi(C.F.F,1) > hi(C.F.S,2)){
            C = {{0,0},B.F.F};
            if(B.F.F < B.F.S) C.F.S = B.F.S;
        }
    }
    //printf(" : %d %d %d\n",C.F.F,C.F.S,C.S);
    return C;
}

void update(node *pos,int be,int ed,int x,int y,int o,int i){
    //printf("!!! %d %d \n",be,ed);
    if(pos->lazy != make_pair(make_pair(0,0),0)){
        v = pos->lazy;
        pos->lazy = {{0,0},0};
        if(be != ed) pos->l->lazy = merge(pos->l->lazy,v), pos->r->lazy = merge(pos->r->lazy,v);
        else{
            if(v.S) pos->val = v.S;
            if(hi(pos->val,3) < hi(v.F.F,1)) pos->val = v.F.F;
            if(hi(pos->val,3) > hi(v.F.S,2)) pos->val = v.F.S;
        }
    }
    if(be > ed || ed < x || y < be) return;
    if(x <= be && ed <= y){
        v = (o == 1) ? make_pair(make_pair(i,0),0) : make_pair(make_pair(0,i),0);
        if(be != ed) pos->l->lazy = merge(pos->l->lazy,v), pos->r->lazy = merge(pos->r->lazy,v);
        else{
            if(v.S) pos->val = v.S;
            if(hi(pos->val,3) < hi(v.F.F,1)) pos->val = v.F.F;
            if(hi(pos->val,3) > hi(v.F.S,2)) pos->val = v.F.S;
        }
        return;
    }
    int mid = (be+ed)/2;
    update(pos->l,be,mid,x,y,o,i), update(pos->r,mid+1,ed,x,y,o,i);
}

int query(node *pos,int be,int ed,int x){
    if(pos->lazy != make_pair(make_pair(0,0),0)){
        v = pos->lazy;
        pos->lazy = {{0,0},0};
        if(be != ed) pos->l->lazy = merge(pos->l->lazy,v), pos->r->lazy = merge(pos->r->lazy,v);
        else{
            if(v.S) pos->val = v.S;
            if(hi(pos->val,3) < hi(v.F.F,1)) pos->val = v.F.F;
            if(hi(pos->val,3) > hi(v.F.S,2)) pos->val = v.F.S;
        }
    }
    if(be > ed || ed < x || x < be) return -1;
    if(be == ed) return pos->val;
    int mid = (be+ed)/2;
    return max(query(pos->l,be,mid,x), query(pos->r,mid+1,ed,x));
}

void buildWall(int N, int K, int OP[], int left[], int right[], int height[], int finalHeight[]){
    n = N, k = K;
    for(int i=1;i<=k;i++) op[i] = OP[i-1], l[i] = left[i-1]+1, r[i] = right[i-1]+1, h[i] = height[i-1];
    build(&top,1,n);
    for(int i=1;i<=k;i++){
        update(&top,1,n,l[i],r[i],op[i],i);
        //for(int i=1;i<=n;i++) printf("%d ",query(&top,1,n,i));
        //printf("\n\n");
    }
    for(int i=1;i<=n;i++){
        finalHeight[i-1] = h[query(&top,1,n,i)];
    }
    return;
}

/*
4 4
1 0 3 11
2 1 3 2
1 2 3 3
2 3 3 1
*/

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