oj.uz

Submission #899778

# Submission time Handle Problem Language Result Execution time Memory
899778 2024-01-07T01:28:03 Z ByeWorld Wall (IOI14_wall) C++14
100 / 100
 525 ms 95572 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e6+20;
const int LOG = 60;
const int MOD = 998244353;
const int SQRT = 520;
const int INF = 2e9+10;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
 
int n, q;
int ans[MAXN];

struct node {
    int laz;
    int mn, mx;
} st[4*MAXN];

struct segtree {
    void merge(int id){
        // mx
        st[id].mx = max(st[lf].mx, st[rg].mx);
        st[id].mn = min(st[lf].mn, st[rg].mn);
        st[id].laz = -1;
    }
    void bd(int id, int l, int r){
        st[id].laz = -1;
        if(l==r){
            st[id].mn = st[id].mx = 0;
            return;
        }
        bd(lf, l, md); bd(rg, md+1, r);
        merge(id);
    }
    void push(int id, int l, int r, int p){
        st[id].mx = st[id].mn = p; 
        st[id].laz = p;
    }
    void bnc(int id, int l, int r){
        if(l==r || st[id].laz == -1) return;
        push(lf, l, md, st[id].laz);
        push(rg, md+1, r, st[id].laz);
        st[id].laz = -1;
    }
    void CHMX(int id, int l, int r, int x, int y, int p){
        if(r<x || y<l || st[id].mn >= p) return;
        if(x<=l && r<=y && st[id].mx <= p){ // keganti semua
            push(id, l, r, p); return;
        }
        bnc(id, l, r);
        CHMX(lf, l, md, x, y, p); CHMX(rg, md+1, r, x, y, p);
        merge(id);
    }
    void CHMN(int id, int l, int r, int x, int y, int p){
        if(r<x || y<l || st[id].mx <= p) return;
        if(x<=l && r<=y && st[id].mn >= p){ // keganti semua
            push(id, l, r, p); return;
        }
        bnc(id, l, r);
        CHMN(lf, l, md, x, y, p); CHMN(rg, md+1, r, x, y, p);
        merge(id);
    }
    
    void que(int id, int l, int r){
        if(l==r){ ans[l] = st[id].mx; return; }
        bnc(id, l, r);
        que(lf, l, md); que(rg, md+1, r);
    }
} A;

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    n = N;
    A.bd(1, 1, n);
    for(int i=0; i<k; i++){
        left[i]++; right[i]++;
        if(op[i]==1){ // a[i] = max(a[i], x)
            A.CHMX(1, 1, n, left[i], right[i], height[i]);
        } else {
            A.CHMN(1, 1, n, left[i], right[i], height[i]);
        }
    }
    A.que(1, 1, n);
    for(int i=0; i<n; i++) finalHeight[i] = ans[i+1];
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 108 ms 10320 KB Output is correct
3 Correct 53 ms 8020 KB Output is correct
4 Correct 134 ms 15040 KB Output is correct
5 Correct 134 ms 15680 KB Output is correct
6 Correct 144 ms 15600 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 5 ms 4700 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 108 ms 10204 KB Output is correct
9 Correct 53 ms 8020 KB Output is correct
10 Correct 163 ms 15100 KB Output is correct
11 Correct 140 ms 15440 KB Output is correct
12 Correct 143 ms 15444 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 113 ms 10168 KB Output is correct
15 Correct 19 ms 5208 KB Output is correct
16 Correct 314 ms 15296 KB Output is correct
17 Correct 205 ms 15188 KB Output is correct
18 Correct 197 ms 15188 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 4 ms 4656 KB Output is correct
5 Correct 5 ms 4696 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 108 ms 10300 KB Output is correct
9 Correct 53 ms 8020 KB Output is correct
10 Correct 139 ms 15052 KB Output is correct
11 Correct 136 ms 15452 KB Output is correct
12 Correct 149 ms 15444 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 111 ms 10084 KB Output is correct
15 Correct 21 ms 5212 KB Output is correct
16 Correct 305 ms 15380 KB Output is correct
17 Correct 197 ms 15184 KB Output is correct
18 Correct 206 ms 15184 KB Output is correct
19 Correct 473 ms 84820 KB Output is correct
20 Correct 470 ms 92756 KB Output is correct
21 Correct 469 ms 95316 KB Output is correct
22 Correct 463 ms 92924 KB Output is correct
23 Correct 465 ms 93008 KB Output is correct
24 Correct 474 ms 93112 KB Output is correct
25 Correct 468 ms 92952 KB Output is correct
26 Correct 472 ms 95496 KB Output is correct
27 Correct 476 ms 95572 KB Output is correct
28 Correct 525 ms 92932 KB Output is correct
29 Correct 464 ms 92756 KB Output is correct
30 Correct 472 ms 92876 KB Output is correct