oj.uz

Submission #1047817

# Submission time Handle Problem Language Result Execution time Memory
1047817 2024-08-07T16:14:20 Z adelcidp Wall (IOI14_wall) C++17
100 / 100
 432 ms 111184 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 4540 KB Output is correct
2 Correct 1 ms 4676 KB Output is correct
3 Correct 1 ms 4604 KB Output is correct
4 Correct 4 ms 5144 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 68 ms 18160 KB Output is correct
3 Correct 110 ms 12340 KB Output is correct
4 Correct 320 ms 25684 KB Output is correct
5 Correct 178 ms 26712 KB Output is correct
6 Correct 164 ms 25080 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 4660 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 5 ms 5208 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 3 ms 5000 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 71 ms 17976 KB Output is correct
9 Correct 112 ms 12372 KB Output is correct
10 Correct 321 ms 25540 KB Output is correct
11 Correct 171 ms 26704 KB Output is correct
12 Correct 165 ms 24988 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 73 ms 18192 KB Output is correct
15 Correct 22 ms 6484 KB Output is correct
16 Correct 393 ms 25684 KB Output is correct
17 Correct 175 ms 25172 KB Output is correct
18 Correct 176 ms 25172 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 1 ms 4444 KB Output is correct
4 Correct 4 ms 5144 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 70 ms 17984 KB Output is correct
9 Correct 119 ms 12368 KB Output is correct
10 Correct 322 ms 25684 KB Output is correct
11 Correct 170 ms 26708 KB Output is correct
12 Correct 165 ms 25116 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 68 ms 18112 KB Output is correct
15 Correct 26 ms 6492 KB Output is correct
16 Correct 392 ms 25940 KB Output is correct
17 Correct 172 ms 25172 KB Output is correct
18 Correct 171 ms 25108 KB Output is correct
19 Correct 415 ms 111184 KB Output is correct
20 Correct 411 ms 108628 KB Output is correct
21 Correct 420 ms 111184 KB Output is correct
22 Correct 412 ms 108636 KB Output is correct
23 Correct 408 ms 108740 KB Output is correct
24 Correct 410 ms 108920 KB Output is correct
25 Correct 405 ms 108624 KB Output is correct
26 Correct 407 ms 111184 KB Output is correct
27 Correct 431 ms 111164 KB Output is correct
28 Correct 432 ms 108624 KB Output is correct
29 Correct 415 ms 108716 KB Output is correct
30 Correct 419 ms 108624 KB Output is correct