oj.uz

Submission #596113

# Submission time Handle Problem Language Result Execution time Memory
596113 2022-07-14T11:46:01 Z neki Wall (IOI14_wall) C++14
100 / 100
 650 ms 69616 KB 
#include <bits/stdc++.h>
#define vc vector

using namespace std;

const int mn=2000000;
int tl[4 * mn], tr[4 * mn];

void apply(int no, int m, int M){
    if(tr[no]<=m) tl[no]=tr[no]=m;
    else if(M<=tl[no]) tl[no]=tr[no]=M;
    else tl[no]=max(tl[no], m), tr[no]=min(tr[no], M);
}
void push(int no){
    apply(no * 2 +1, tl[no], tr[no]);
    apply(no * 2 +2, tl[no], tr[no]);
    tl[no]=0, tr[no]=INT_MAX;
}
void update(int ql, int qr, int m, int M, int l, int r, int no){
    if(ql==l and qr==r) apply(no, m, M);
    else{
        int mid=(l+r)/2;
        push(no);
        if(qr<=mid) update(ql, qr, m, M, l, mid, no * 2 +1);
        else if(mid<ql) update(ql, qr, m, M, mid+1, r, no * 2 +2);
        else update(ql, mid, m, M, l, mid, no * 2 + 1), update(mid+1, qr, m, M, mid+1, r, no * 2 +2);
    }
}
void build(int l, int r, int no, int ans[]){
    if(l==r) ans[l]=tl[no];
    else{
        int mid=(l+r)/2;
        push(no);
        build(l, mid, no * 2 +1, ans);
        build(mid+1, r, no * 2 + 2, ans);
    }
}

void buildWall(int n, int k, int op[], int ql[], int qr[], int h[], int ans[]){
    for(int i=0;i<k;++i){
        if(op[i]==1) update(ql[i], qr[i], h[i], INT_MAX, 0, n-1, 0);
        if(op[i]==2) update(ql[i], qr[i], 0, h[i], 0, n-1, 0);
    }
    build(0, n-1, 0, ans);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 444 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 828 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 124 ms 13836 KB Output is correct
3 Correct 139 ms 7884 KB Output is correct
4 Correct 385 ms 20380 KB Output is correct
5 Correct 255 ms 21372 KB Output is correct
6 Correct 237 ms 19788 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 388 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 129 ms 13848 KB Output is correct
9 Correct 141 ms 7940 KB Output is correct
10 Correct 384 ms 20392 KB Output is correct
11 Correct 270 ms 21412 KB Output is correct
12 Correct 236 ms 19812 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 168 ms 13896 KB Output is correct
15 Correct 28 ms 1996 KB Output is correct
16 Correct 486 ms 20580 KB Output is correct
17 Correct 261 ms 19992 KB Output is correct
18 Correct 247 ms 20152 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 5 ms 828 KB Output is correct
6 Correct 6 ms 836 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 123 ms 13956 KB Output is correct
9 Correct 138 ms 7920 KB Output is correct
10 Correct 398 ms 20352 KB Output is correct
11 Correct 262 ms 21380 KB Output is correct
12 Correct 246 ms 19756 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 169 ms 13896 KB Output is correct
15 Correct 29 ms 1976 KB Output is correct
16 Correct 471 ms 20572 KB Output is correct
17 Correct 248 ms 20028 KB Output is correct
18 Correct 246 ms 20008 KB Output is correct
19 Correct 623 ms 69616 KB Output is correct
20 Correct 622 ms 66972 KB Output is correct
21 Correct 624 ms 69476 KB Output is correct
22 Correct 616 ms 67168 KB Output is correct
23 Correct 626 ms 66980 KB Output is correct
24 Correct 621 ms 66936 KB Output is correct
25 Correct 650 ms 67020 KB Output is correct
26 Correct 617 ms 69448 KB Output is correct
27 Correct 623 ms 69532 KB Output is correct
28 Correct 620 ms 66996 KB Output is correct
29 Correct 624 ms 66940 KB Output is correct
30 Correct 621 ms 66952 KB Output is correct