oj.uz

Submission #881205

# Submission time Handle Problem Language Result Execution time Memory
881205 2023-11-30T21:24:10 Z MarwenElarbi Wall (IOI14_wall) C++17
100 / 100
 631 ms 100820 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 4444 KB Output is correct
2 Correct 2 ms 4612 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 6 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 4 ms 4956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 109 ms 12316 KB Output is correct
3 Correct 158 ms 8672 KB Output is correct
4 Correct 446 ms 15972 KB Output is correct
5 Correct 255 ms 16484 KB Output is correct
6 Correct 233 ms 16464 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 6 ms 5048 KB Output is correct
5 Correct 5 ms 4956 KB Output is correct
6 Correct 6 ms 4956 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 111 ms 12380 KB Output is correct
9 Correct 155 ms 8532 KB Output is correct
10 Correct 457 ms 15976 KB Output is correct
11 Correct 234 ms 16464 KB Output is correct
12 Correct 233 ms 16464 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 117 ms 12140 KB Output is correct
15 Correct 29 ms 5712 KB Output is correct
16 Correct 536 ms 16236 KB Output is correct
17 Correct 238 ms 16212 KB Output is correct
18 Correct 237 ms 16208 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 6 ms 4952 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 4 ms 4956 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 110 ms 12364 KB Output is correct
9 Correct 155 ms 8532 KB Output is correct
10 Correct 446 ms 15952 KB Output is correct
11 Correct 263 ms 16636 KB Output is correct
12 Correct 233 ms 16472 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 132 ms 12316 KB Output is correct
15 Correct 36 ms 5808 KB Output is correct
16 Correct 522 ms 16432 KB Output is correct
17 Correct 239 ms 16288 KB Output is correct
18 Correct 241 ms 16088 KB Output is correct
19 Correct 575 ms 100760 KB Output is correct
20 Correct 575 ms 98132 KB Output is correct
21 Correct 571 ms 100544 KB Output is correct
22 Correct 577 ms 98452 KB Output is correct
23 Correct 570 ms 98084 KB Output is correct
24 Correct 631 ms 98124 KB Output is correct
25 Correct 605 ms 98436 KB Output is correct
26 Correct 623 ms 100748 KB Output is correct
27 Correct 577 ms 100820 KB Output is correct
28 Correct 575 ms 98168 KB Output is correct
29 Correct 606 ms 98320 KB Output is correct
30 Correct 627 ms 98336 KB Output is correct