oj.uz

Submission #1015701

# Submission time Handle Problem Language Result Execution time Memory
1015701 2024-07-06T16:44:50 Z dpsaveslives Wall (IOI14_wall) C++17
100 / 100
 368 ms 69640 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
pair<int,int> segtree[8000000];
const int INF = 2e9+20;
const pair<int,int> wert = {-INF,INF};
int N;
void build(int l = 0, int r = N-1, int p = 1){
    if(l == 0 && r == N-1){
        segtree[p].f = segtree[p].s = 0;
    }
    else{
        segtree[p].f = -INF; segtree[p].s = INF;
    }
    if(l == r){
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,p<<1); build(mid+1,r,(p<<1)|1);
}
void push(int p, pair<int,int> newval){
    if(newval.s < segtree[p].f){
        segtree[p] = {newval.s,newval.s};
        return;
    }
    if(segtree[p].s < newval.f){
        segtree[p] = {newval.f,newval.f};
        return;
    }
    segtree[p] = {max(newval.f,segtree[p].f),min(newval.s,segtree[p].s)};
}
void pushtochild(int p){
    if(segtree[p] == wert) return;
    push(p<<1,segtree[p]);
    push((p<<1)|1,segtree[p]);
    segtree[p].f = -INF; segtree[p].s = INF;
}
void upd(int tarl, int tarr, pair<int,int> val, int l = 0, int r = N-1, int p = 1){
    if(r < tarl || l > tarr) return;
    if(tarl <= l && r <= tarr){
        push(p,val);
        return;
    }
    int mid = (l+r)>>1;
    if(l != r){
        pushtochild(p);
    }
    upd(tarl,tarr,val,l,mid,p<<1); upd(tarl,tarr,val,mid+1,r,(p<<1)|1);
}
void query(int* ans, int l = 0, int r = N-1, int p = 1){
    if(l == r){
        ans[l] = segtree[p].f;
        return;
    }
    else{
        pushtochild(p);
    }
    int mid = (l+r)>>1;
    query(ans,l,mid,p<<1); query(ans,mid+1,r,(p<<1)|1);

}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N = n;
    build();
    for(int i = 0;i<k;++i){
        if(op[i] == 1){
            pair<int,int> val; val.s = INF; val.f = height[i];
            upd(left[i],right[i],val);
        }
        else{
            pair<int,int> val; val.f = -INF; val.s = height[i];
            upd(left[i],right[i],val);
        }
    }
    query(finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 708 KB Output is correct
5 Correct 3 ms 900 KB Output is correct
6 Correct 3 ms 900 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 78 ms 8040 KB Output is correct
3 Correct 107 ms 4328 KB Output is correct
4 Correct 285 ms 15840 KB Output is correct
5 Correct 164 ms 21588 KB Output is correct
6 Correct 143 ms 19768 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 744 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 5 ms 904 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 13848 KB Output is correct
9 Correct 105 ms 8016 KB Output is correct
10 Correct 281 ms 20308 KB Output is correct
11 Correct 163 ms 21416 KB Output is correct
12 Correct 151 ms 19792 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 81 ms 13904 KB Output is correct
15 Correct 22 ms 2136 KB Output is correct
16 Correct 353 ms 20564 KB Output is correct
17 Correct 165 ms 20048 KB Output is correct
18 Correct 157 ms 20180 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 712 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 87 ms 13940 KB Output is correct
9 Correct 102 ms 8056 KB Output is correct
10 Correct 278 ms 20308 KB Output is correct
11 Correct 148 ms 21584 KB Output is correct
12 Correct 144 ms 19940 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 89 ms 13912 KB Output is correct
15 Correct 22 ms 2136 KB Output is correct
16 Correct 362 ms 20584 KB Output is correct
17 Correct 160 ms 20048 KB Output is correct
18 Correct 151 ms 20048 KB Output is correct
19 Correct 349 ms 69476 KB Output is correct
20 Correct 325 ms 67152 KB Output is correct
21 Correct 334 ms 69460 KB Output is correct
22 Correct 343 ms 67016 KB Output is correct
23 Correct 327 ms 66964 KB Output is correct
24 Correct 327 ms 67148 KB Output is correct
25 Correct 332 ms 67152 KB Output is correct
26 Correct 334 ms 69456 KB Output is correct
27 Correct 349 ms 69640 KB Output is correct
28 Correct 330 ms 67056 KB Output is correct
29 Correct 358 ms 66972 KB Output is correct
30 Correct 368 ms 67156 KB Output is correct