oj.uz

Submission #711511

# Submission time Handle Problem Language Result Execution time Memory
711511 2023-03-17T06:39:15 Z Pherokung Wall (IOI14_wall) C++14
100 / 100
 1354 ms 232380 KB 
#include "wall.h"
#include<bits/stdc++.h>
#define MAXK 500005
#define F first
#define S second
#define INF 1000000007
using namespace std;
typedef pair<int,int> pa;
int n,k,op[MAXK],l[MAXK],r[MAXK],hi[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 = {-1,-2};
        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 = {-1,-2};
}

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

pa merge(pa A,pa B){ // A = OLD, B = NEW
    pa C;
    C.F = (h(A.F) > h(B.F)) ? A.F : B.F;
    C.S = (h(A.S) < h(B.S)) ? A.S : B.S;
    if(h(C.F) > h(C.S)){
        if(C.F > C.S) C.S = C.F;
        else C.F = 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(-1,-2)){
        v = pos->lazy;
        pos->lazy = {-1,-2};
        if(be != ed) pos->l->lazy = merge(pos->l->lazy,v), pos->r->lazy = merge(pos->r->lazy,v);
        else{
            if(h(pos->val) < h(v.F)) pos->val = v.F;
            if(h(pos->val) > h(v.S)) pos->val = v.S;
        }
    }
    if(be > ed || ed < x || y < be) return;
    if(x <= be && ed <= y){
        v = (o == 1) ? make_pair(i,-2) : make_pair(-1,i);
        if(be != ed) pos->l->lazy = merge(pos->l->lazy,v), pos->r->lazy = merge(pos->r->lazy,v);
        else{
            if(h(pos->val) < h(v.F)) pos->val = v.F;
            if(h(pos->val) > h(v.S)) pos->val = v.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(-1,-2)){
        v = pos->lazy;
        pos->lazy = {-1,-2};
        if(be != ed) pos->l->lazy = merge(pos->l->lazy,v), pos->r->lazy = merge(pos->r->lazy,v);
        else{
            if(h(pos->val) < h(v.F)) pos->val = v.F;
            if(h(pos->val) > h(v.S)) pos->val = v.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, hi[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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 3 ms 448 KB Output is correct
4 Correct 11 ms 1556 KB Output is correct
5 Correct 7 ms 1620 KB Output is correct
6 Correct 7 ms 1556 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 181 ms 21708 KB Output is correct
3 Correct 323 ms 12392 KB Output is correct
4 Correct 999 ms 35444 KB Output is correct
5 Correct 297 ms 36560 KB Output is correct
6 Correct 309 ms 34968 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 360 KB Output is correct
4 Correct 12 ms 1620 KB Output is correct
5 Correct 7 ms 1556 KB Output is correct
6 Correct 10 ms 1552 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 178 ms 21764 KB Output is correct
9 Correct 367 ms 12364 KB Output is correct
10 Correct 1176 ms 35492 KB Output is correct
11 Correct 297 ms 36632 KB Output is correct
12 Correct 275 ms 34968 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 132 ms 21864 KB Output is correct
15 Correct 74 ms 3592 KB Output is correct
16 Correct 1253 ms 35740 KB Output is correct
17 Correct 338 ms 35164 KB Output is correct
18 Correct 288 ms 35128 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 4 ms 448 KB Output is correct
4 Correct 15 ms 1552 KB Output is correct
5 Correct 10 ms 1492 KB Output is correct
6 Correct 8 ms 1596 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 132 ms 21688 KB Output is correct
9 Correct 320 ms 12368 KB Output is correct
10 Correct 1075 ms 35528 KB Output is correct
11 Correct 296 ms 36588 KB Output is correct
12 Correct 272 ms 34940 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 132 ms 21712 KB Output is correct
15 Correct 66 ms 3612 KB Output is correct
16 Correct 1199 ms 35772 KB Output is correct
17 Correct 278 ms 35152 KB Output is correct
18 Correct 306 ms 35308 KB Output is correct
19 Correct 1297 ms 232376 KB Output is correct
20 Correct 1303 ms 229764 KB Output is correct
21 Correct 1344 ms 232368 KB Output is correct
22 Correct 1294 ms 229868 KB Output is correct
23 Correct 1342 ms 229792 KB Output is correct
24 Correct 1294 ms 229832 KB Output is correct
25 Correct 1335 ms 229860 KB Output is correct
26 Correct 1273 ms 232316 KB Output is correct
27 Correct 1354 ms 232380 KB Output is correct
28 Correct 1254 ms 229748 KB Output is correct
29 Correct 1340 ms 229884 KB Output is correct
30 Correct 1307 ms 229908 KB Output is correct