oj.uz

Submission #478923

# Submission time Handle Problem Language Result Execution time Memory
478923 2021-10-09T06:34:00 Z MohammadAghil Wall (IOI14_wall) C++14
100 / 100
 923 ms 110152 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 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 1100 KB Output is correct
5 Correct 6 ms 1112 KB Output is correct
6 Correct 5 ms 1100 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 160 ms 10028 KB Output is correct
3 Correct 210 ms 6684 KB Output is correct
4 Correct 661 ms 15160 KB Output is correct
5 Correct 347 ms 23892 KB Output is correct
6 Correct 325 ms 22284 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 1028 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 5 ms 1100 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 159 ms 10048 KB Output is correct
9 Correct 221 ms 6728 KB Output is correct
10 Correct 622 ms 15084 KB Output is correct
11 Correct 356 ms 23932 KB Output is correct
12 Correct 321 ms 22256 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 156 ms 13888 KB Output is correct
15 Correct 40 ms 2600 KB Output is correct
16 Correct 788 ms 23036 KB Output is correct
17 Correct 333 ms 22476 KB Output is correct
18 Correct 347 ms 22428 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 1080 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 154 ms 9964 KB Output is correct
9 Correct 247 ms 6724 KB Output is correct
10 Correct 665 ms 15056 KB Output is correct
11 Correct 338 ms 23920 KB Output is correct
12 Correct 353 ms 22216 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 164 ms 14292 KB Output is correct
15 Correct 41 ms 2500 KB Output is correct
16 Correct 723 ms 23044 KB Output is correct
17 Correct 337 ms 22568 KB Output is correct
18 Correct 361 ms 22428 KB Output is correct
19 Correct 923 ms 110152 KB Output is correct
20 Correct 831 ms 107584 KB Output is correct
21 Correct 869 ms 110144 KB Output is correct
22 Correct 810 ms 107764 KB Output is correct
23 Correct 841 ms 107720 KB Output is correct
24 Correct 863 ms 107716 KB Output is correct
25 Correct 867 ms 107568 KB Output is correct
26 Correct 832 ms 110144 KB Output is correct
27 Correct 841 ms 110136 KB Output is correct
28 Correct 832 ms 107652 KB Output is correct
29 Correct 844 ms 107712 KB Output is correct
30 Correct 812 ms 107616 KB Output is correct