oj.uz

Submission #701662

# Submission time Handle Problem Language Result Execution time Memory
701662 2023-02-21T18:38:59 Z Denkata Wall (IOI14_wall) C++14
100 / 100
 733 ms 110148 KB 
#include <bits/stdc++.h> 
#include "wall.h"
using  namespace std;
typedef  long long ll;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 
 
const ll mod = 998244353, maxn = 2e6 + 5, inf = 1e9 + 5;

int mi[maxn << 2], mx[maxn << 2], n, res[maxn];
pp lazy[maxn << 2];

void pull_add(int x, int k){
    mi[x] = max(mi[x], k);
    mx[x] = max(mx[x], k);
    lazy[x].ff = max(lazy[x].ff, k);
    lazy[x].ss = max(lazy[x].ss, k);
}

void pull_dec(int x, int k){
    mi[x] = min(mi[x], k);
    mx[x] = min(mx[x], k);
    lazy[x].ff = min(lazy[x].ff, k);
    lazy[x].ss = min(lazy[x].ss, k);
}

void shift(int x){
    if(lazy[x].ff != -inf){
        pull_add(x << 1, lazy[x].ff);
        pull_add(x << 1 | 1, lazy[x].ff);
    }
    if(lazy[x].ss != inf){
        pull_dec(x << 1, lazy[x].ss);
        pull_dec(x << 1 | 1, lazy[x].ss);
    }
    lazy[x] = {-inf, inf};
}

void upd(int l, int r, int k, int t, int x = 1, int lx = 0, int rx = n){
    if(l <= lx && r >= rx){ // t == 1 -> set_min, else -> set_max
        if(t == 1){
            pull_add(x, k);
        }else{
            pull_dec(x, k);
        }
        return;
    } if(l >= rx || r <= lx) return;
    shift(x);
    int mid = (lx + rx) >> 1;
    upd(l, r, k, t, x << 1, lx, mid);
    upd(l, r, k, t, x << 1 | 1, mid, rx);
    mi[x] = min(mi[x << 1], mi[x << 1 | 1]);
    mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}

void get(int x = 1, int lx = 0, int rx = n){
    if(lx + 1 == rx){
        res[lx] = mi[x];
        return;
    }
    shift(x);
    int mid = (lx + rx) >> 1;
    get(x << 1, lx, mid);
    get(x << 1 | 1, mid, rx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	::n = n;
    rep(i,0,k) upd(left[i], right[i] + 1, height[i], op[i]);
    get();
    rep(i,0,n) finalHeight[i] = res[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 976 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 137 ms 8084 KB Output is correct
3 Correct 180 ms 4684 KB Output is correct
4 Correct 492 ms 13236 KB Output is correct
5 Correct 279 ms 13668 KB Output is correct
6 Correct 273 ms 13672 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 1004 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 130 ms 8268 KB Output is correct
9 Correct 181 ms 4788 KB Output is correct
10 Correct 530 ms 13176 KB Output is correct
11 Correct 284 ms 13664 KB Output is correct
12 Correct 271 ms 13652 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 129 ms 8052 KB Output is correct
15 Correct 34 ms 1952 KB Output is correct
16 Correct 609 ms 13412 KB Output is correct
17 Correct 280 ms 13408 KB Output is correct
18 Correct 279 ms 13508 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 980 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 133 ms 8128 KB Output is correct
9 Correct 208 ms 4800 KB Output is correct
10 Correct 507 ms 13256 KB Output is correct
11 Correct 328 ms 13752 KB Output is correct
12 Correct 271 ms 13748 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 142 ms 8192 KB Output is correct
15 Correct 37 ms 1996 KB Output is correct
16 Correct 616 ms 13460 KB Output is correct
17 Correct 348 ms 13528 KB Output is correct
18 Correct 286 ms 13416 KB Output is correct
19 Correct 733 ms 110148 KB Output is correct
20 Correct 728 ms 107596 KB Output is correct
21 Correct 720 ms 110104 KB Output is correct
22 Correct 716 ms 107584 KB Output is correct
23 Correct 674 ms 107612 KB Output is correct
24 Correct 693 ms 107640 KB Output is correct
25 Correct 700 ms 107732 KB Output is correct
26 Correct 695 ms 110148 KB Output is correct
27 Correct 709 ms 110096 KB Output is correct
28 Correct 690 ms 107748 KB Output is correct
29 Correct 693 ms 107824 KB Output is correct
30 Correct 690 ms 107660 KB Output is correct