oj.uz

Submission #1039846

# Submission time Handle Problem Language Result Execution time Memory
1039846 2024-07-31T10:30:57 Z Thunnus Wall (IOI14_wall) C++17
100 / 100
 507 ms 111168 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 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 5 ms 4956 KB Output is correct
5 Correct 4 ms 5136 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 4696 KB Output is correct
2 Correct 80 ms 18004 KB Output is correct
3 Correct 131 ms 12372 KB Output is correct
4 Correct 380 ms 25668 KB Output is correct
5 Correct 208 ms 26688 KB Output is correct
6 Correct 203 ms 25108 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 4 ms 4964 KB Output is correct
6 Correct 4 ms 4956 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 80 ms 18004 KB Output is correct
9 Correct 144 ms 12400 KB Output is correct
10 Correct 369 ms 25424 KB Output is correct
11 Correct 215 ms 26704 KB Output is correct
12 Correct 195 ms 25100 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 81 ms 18000 KB Output is correct
15 Correct 24 ms 6444 KB Output is correct
16 Correct 440 ms 25896 KB Output is correct
17 Correct 204 ms 25172 KB Output is correct
18 Correct 232 ms 25320 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 5 ms 4956 KB Output is correct
5 Correct 4 ms 5004 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 81 ms 18072 KB Output is correct
9 Correct 140 ms 12652 KB Output is correct
10 Correct 372 ms 25428 KB Output is correct
11 Correct 207 ms 26640 KB Output is correct
12 Correct 203 ms 25168 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 82 ms 18148 KB Output is correct
15 Correct 24 ms 6484 KB Output is correct
16 Correct 449 ms 25976 KB Output is correct
17 Correct 198 ms 25216 KB Output is correct
18 Correct 200 ms 25140 KB Output is correct
19 Correct 507 ms 111112 KB Output is correct
20 Correct 492 ms 108628 KB Output is correct
21 Correct 475 ms 111168 KB Output is correct
22 Correct 441 ms 108880 KB Output is correct
23 Correct 459 ms 108628 KB Output is correct
24 Correct 473 ms 108700 KB Output is correct
25 Correct 455 ms 108624 KB Output is correct
26 Correct 453 ms 111168 KB Output is correct
27 Correct 477 ms 111076 KB Output is correct
28 Correct 463 ms 108824 KB Output is correct
29 Correct 458 ms 108636 KB Output is correct
30 Correct 462 ms 108708 KB Output is correct