oj.uz

Submission #899777

# Submission time Handle Problem Language Result Execution time Memory
899777 2024-01-07T01:27:25 Z ByeWorld Wall (IOI14_wall) C++14
61 / 100
 311 ms 43504 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 = 3e5+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 2648 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 4 ms 4740 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 2392 KB Output is correct
2 Correct 111 ms 15956 KB Output is correct
3 Correct 56 ms 11856 KB Output is correct
4 Correct 135 ms 24560 KB Output is correct
5 Correct 137 ms 25620 KB Output is correct
6 Correct 149 ms 24148 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 1 ms 2396 KB Output is correct
4 Correct 5 ms 4740 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 2396 KB Output is correct
8 Correct 118 ms 15948 KB Output is correct
9 Correct 57 ms 11860 KB Output is correct
10 Correct 135 ms 24632 KB Output is correct
11 Correct 140 ms 25684 KB Output is correct
12 Correct 148 ms 24152 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 119 ms 16152 KB Output is correct
15 Correct 18 ms 5716 KB Output is correct
16 Correct 308 ms 24912 KB Output is correct
17 Correct 200 ms 24396 KB Output is correct
18 Correct 201 ms 24396 KB Output is correct

Subtask #4
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 1 ms 2396 KB Output is correct
4 Correct 5 ms 4804 KB Output is correct
5 Correct 4 ms 4952 KB Output is correct
6 Correct 4 ms 4960 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 111 ms 15988 KB Output is correct
9 Correct 59 ms 11856 KB Output is correct
10 Correct 138 ms 24780 KB Output is correct
11 Correct 159 ms 25680 KB Output is correct
12 Correct 150 ms 24400 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 117 ms 16024 KB Output is correct
15 Correct 19 ms 5712 KB Output is correct
16 Correct 311 ms 24916 KB Output is correct
17 Correct 211 ms 24332 KB Output is correct
18 Correct 198 ms 24316 KB Output is correct
19 Runtime error 145 ms 43504 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -