oj.uz

Submission #477536

# Submission time Handle Problem Language Result Execution time Memory
477536 2021-10-02T13:31:43 Z CyberSleeper Wall (IOI14_wall) C++17
100 / 100
 1488 ms 161916 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int MX=2000007, INF=1e9+7;

int N;

struct SegTree{
    #define mi      (le+ri)/2
    #define idxl    (idx*2+1)
    #define idxr    (idx*2+2)

    struct Node{
        int mn, mx, lzmn, lzmx;
        Node(){
            mx=mn=lzmn=0;
            lzmx=INF;
        }
    }id;
    Node combin(Node a, Node b){
        Node ret;
        ret.mn=min(a.mn, b.mn);
        ret.mx=max(a.mx, b.mx);
        return ret;
    }

    Node ST[4*MX];
    int letar, ritar, val, ch;

    void prop(int idx, int le, int ri){
        if(ST[idx].lzmn){
            ST[idx].mn=max(ST[idx].lzmn, ST[idx].mn);
            ST[idx].mx=max(ST[idx].mn, ST[idx].mx);
            if(le<ri){
                ST[idxl].lzmn=max(ST[idxl].lzmn, ST[idx].lzmn);
                ST[idxl].lzmx=max(ST[idxl].lzmx, ST[idxl].lzmn);
                ST[idxr].lzmn=max(ST[idxr].lzmn, ST[idx].lzmn);
                ST[idxr].lzmx=max(ST[idxr].lzmx, ST[idxr].lzmn);
            }
        }
        if(ST[idx].lzmx!=INF){
            ST[idx].mx=min(ST[idx].lzmx, ST[idx].mx);
            ST[idx].mn=min(ST[idx].mx, ST[idx].mn);
            if(le<ri){
                ST[idxl].lzmx=min(ST[idxl].lzmx, ST[idx].lzmx);
                ST[idxl].lzmn=min(ST[idxl].lzmn, ST[idxl].lzmx);
                ST[idxr].lzmx=min(ST[idxr].lzmx, ST[idx].lzmx);
                ST[idxr].lzmn=min(ST[idxr].lzmn, ST[idxr].lzmx);
            }
        }
        ST[idx].lzmn=0;
        ST[idx].lzmx=INF;
    }
    void upd(int idx, int le, int ri){
        prop(idx, le, ri);
        if(ri<letar || ritar<le)
            return;
        if(letar<=le && ri<=ritar){
            if(ch&1){
                ST[idx].lzmn=max(ST[idx].lzmn, val);
                ST[idx].lzmx=max(ST[idx].lzmx, ST[idx].lzmn);
            }else{
                ST[idx].lzmx=min(ST[idx].lzmx, val);
                ST[idx].lzmn=min(ST[idx].lzmn, ST[idx].lzmx);
            }
            prop(idx, le, ri);
            return;
        }
        upd(idxl, le, mi); upd(idxr, mi+1, ri);
        ST[idx]=combin(ST[idxl], ST[idxr]);
    }
    int que(int idx, int le, int ri){
        prop(idx, le, ri);
        if(ri<letar || ritar<le)
            return 0;
        if(letar<=le && ri<=ritar){
            return ST[idx].mn;
        }
        return max(que(idxl, le, mi), que(idxr, mi+1, ri));
    }

    void update(int op, int le, int ri, int v){
        ch=op, letar=le, ritar=ri, val=v;
        upd(0, 0, N-1);
    }
    int query(int x){
        letar=ritar=x;
        return que(0, 0, N-1);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N=n;
    SegTree ST;
    for(int i=0, ch, l, r, h; i<k; i++){
        ch=op[i], l=left[i], r=right[i], h=height[i];
        ST.update(ch, l, r, h);
    }
    for(int i=0; i<N; i++)
        finalHeight[i]=ST.query(i);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 125504 KB Output is correct
2 Correct 68 ms 125536 KB Output is correct
3 Correct 72 ms 125540 KB Output is correct
4 Correct 76 ms 125636 KB Output is correct
5 Correct 76 ms 125768 KB Output is correct
6 Correct 79 ms 125756 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 125464 KB Output is correct
2 Correct 221 ms 133444 KB Output is correct
3 Correct 317 ms 128856 KB Output is correct
4 Correct 849 ms 143504 KB Output is correct
5 Correct 450 ms 144524 KB Output is correct
6 Correct 460 ms 143004 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 125436 KB Output is correct
2 Correct 72 ms 125496 KB Output is correct
3 Correct 77 ms 125480 KB Output is correct
4 Correct 82 ms 125608 KB Output is correct
5 Correct 74 ms 125768 KB Output is correct
6 Correct 74 ms 125700 KB Output is correct
7 Correct 72 ms 125508 KB Output is correct
8 Correct 219 ms 139336 KB Output is correct
9 Correct 318 ms 132656 KB Output is correct
10 Correct 814 ms 143504 KB Output is correct
11 Correct 432 ms 144584 KB Output is correct
12 Correct 434 ms 143000 KB Output is correct
13 Correct 66 ms 125512 KB Output is correct
14 Correct 227 ms 139124 KB Output is correct
15 Correct 114 ms 126620 KB Output is correct
16 Correct 917 ms 143756 KB Output is correct
17 Correct 449 ms 143188 KB Output is correct
18 Correct 430 ms 143232 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 125512 KB Output is correct
2 Correct 73 ms 125588 KB Output is correct
3 Correct 79 ms 125620 KB Output is correct
4 Correct 80 ms 125696 KB Output is correct
5 Correct 77 ms 125712 KB Output is correct
6 Correct 76 ms 125756 KB Output is correct
7 Correct 72 ms 125424 KB Output is correct
8 Correct 228 ms 139180 KB Output is correct
9 Correct 313 ms 132680 KB Output is correct
10 Correct 770 ms 143504 KB Output is correct
11 Correct 446 ms 144560 KB Output is correct
12 Correct 427 ms 142960 KB Output is correct
13 Correct 67 ms 125520 KB Output is correct
14 Correct 234 ms 139104 KB Output is correct
15 Correct 113 ms 126704 KB Output is correct
16 Correct 899 ms 143760 KB Output is correct
17 Correct 445 ms 143160 KB Output is correct
18 Correct 438 ms 143176 KB Output is correct
19 Correct 1427 ms 161852 KB Output is correct
20 Correct 1408 ms 159468 KB Output is correct
21 Correct 1400 ms 161916 KB Output is correct
22 Correct 1412 ms 159348 KB Output is correct
23 Correct 1432 ms 159436 KB Output is correct
24 Correct 1465 ms 159432 KB Output is correct
25 Correct 1448 ms 159356 KB Output is correct
26 Correct 1472 ms 161884 KB Output is correct
27 Correct 1455 ms 161832 KB Output is correct
28 Correct 1488 ms 159432 KB Output is correct
29 Correct 1480 ms 159640 KB Output is correct
30 Correct 1441 ms 159576 KB Output is correct