oj.uz

Submission #624557

# Submission time Handle Problem Language Result Execution time Memory
624557 2022-08-08T13:01:43 Z DeMen100ns Wall (IOI14_wall) C++17
100 / 100
 722 ms 110292 KB 
//icant :)

#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 1 ms 312 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 1024 KB Output is correct
5 Correct 5 ms 1148 KB Output is correct
6 Correct 5 ms 1092 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 131 ms 13880 KB Output is correct
3 Correct 179 ms 8456 KB Output is correct
4 Correct 520 ms 22852 KB Output is correct
5 Correct 284 ms 23820 KB Output is correct
6 Correct 330 ms 22396 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 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 4 ms 1152 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 131 ms 13872 KB Output is correct
9 Correct 187 ms 8520 KB Output is correct
10 Correct 529 ms 22760 KB Output is correct
11 Correct 290 ms 23884 KB Output is correct
12 Correct 270 ms 22332 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 136 ms 13960 KB Output is correct
15 Correct 34 ms 2536 KB Output is correct
16 Correct 619 ms 23016 KB Output is correct
17 Correct 288 ms 22484 KB Output is correct
18 Correct 278 ms 22440 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 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 129 ms 13876 KB Output is correct
9 Correct 187 ms 8520 KB Output is correct
10 Correct 523 ms 22760 KB Output is correct
11 Correct 293 ms 23820 KB Output is correct
12 Correct 287 ms 22328 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 133 ms 13904 KB Output is correct
15 Correct 33 ms 2508 KB Output is correct
16 Correct 605 ms 23016 KB Output is correct
17 Correct 280 ms 22456 KB Output is correct
18 Correct 291 ms 22736 KB Output is correct
19 Correct 678 ms 110128 KB Output is correct
20 Correct 678 ms 107752 KB Output is correct
21 Correct 722 ms 110144 KB Output is correct
22 Correct 679 ms 107656 KB Output is correct
23 Correct 670 ms 107580 KB Output is correct
24 Correct 694 ms 107604 KB Output is correct
25 Correct 671 ms 107668 KB Output is correct
26 Correct 711 ms 110092 KB Output is correct
27 Correct 679 ms 110292 KB Output is correct
28 Correct 676 ms 107572 KB Output is correct
29 Correct 663 ms 107656 KB Output is correct
30 Correct 692 ms 107660 KB Output is correct