oj.uz

Submission #889014

# Submission time Handle Problem Language Result Execution time Memory
889014 2023-12-18T15:25:06 Z BBart888 Wall (IOI14_wall) C++14
100 / 100
 687 ms 111188 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 4444 KB Output is correct
3 Correct 2 ms 4444 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 4992 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 110 ms 12204 KB Output is correct
3 Correct 155 ms 8624 KB Output is correct
4 Correct 442 ms 23616 KB Output is correct
5 Correct 266 ms 26708 KB Output is correct
6 Correct 237 ms 24912 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 4956 KB Output is correct
5 Correct 5 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 112 ms 16976 KB Output is correct
9 Correct 165 ms 11728 KB Output is correct
10 Correct 448 ms 23708 KB Output is correct
11 Correct 241 ms 26704 KB Output is correct
12 Correct 246 ms 25112 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 112 ms 18184 KB Output is correct
15 Correct 30 ms 6360 KB Output is correct
16 Correct 531 ms 25856 KB Output is correct
17 Correct 281 ms 25296 KB Output is correct
18 Correct 245 ms 25280 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 5136 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 111 ms 16840 KB Output is correct
9 Correct 159 ms 11600 KB Output is correct
10 Correct 442 ms 23740 KB Output is correct
11 Correct 246 ms 26660 KB Output is correct
12 Correct 234 ms 25096 KB Output is correct
13 Correct 1 ms 4696 KB Output is correct
14 Correct 113 ms 18188 KB Output is correct
15 Correct 29 ms 6484 KB Output is correct
16 Correct 540 ms 25852 KB Output is correct
17 Correct 242 ms 25168 KB Output is correct
18 Correct 240 ms 25168 KB Output is correct
19 Correct 573 ms 111184 KB Output is correct
20 Correct 567 ms 108628 KB Output is correct
21 Correct 619 ms 111124 KB Output is correct
22 Correct 580 ms 108628 KB Output is correct
23 Correct 565 ms 108592 KB Output is correct
24 Correct 636 ms 108728 KB Output is correct
25 Correct 687 ms 108852 KB Output is correct
26 Correct 572 ms 111132 KB Output is correct
27 Correct 577 ms 111188 KB Output is correct
28 Correct 572 ms 108472 KB Output is correct
29 Correct 577 ms 108940 KB Output is correct
30 Correct 572 ms 108876 KB Output is correct