oj.uz

Submission #1015660

# Submission time Handle Problem Language Result Execution time Memory
1015660 2024-07-06T16:11:41 Z dpsaveslives Wall (IOI14_wall) C++17
0 / 100
 373 ms 20564 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

const int MAXN = 1<<22;
pair<int,int> segtree[MAXN];
const int INF = 1e9;
int N;
void build(int l = 0, int r = N-1, int p = 1){
    if(l == r){
        segtree[p].f = -INF;
        segtree[p].s = INF;
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,p<<1); build(mid+1,r,(p<<1)|1);
    segtree[p].f = -INF; segtree[p].s = INF;
}
void push(int p, pair<int,int> newval){
    if(newval.f > segtree[p].f){
        segtree[p].f = newval.f;
        if(segtree[p].f > segtree[p].s){
            segtree[p].s = segtree[p].f;
        }
    }
    if(newval.s < segtree[p].s){
        segtree[p].s = newval.s;
        if(segtree[p].f > segtree[p].s){
            segtree[p].f = segtree[p].s;
        }
    }
}
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){
        if(segtree[p].f != -INF || segtree[p].s != INF){
            push((p<<1),segtree[p]); push((p<<1)|1,segtree[p]);
            segtree[p].f = -INF; segtree[p].s = INF;
        }
    }
    if(l <= mid){
        upd(tarl,tarr,val,l,mid,p<<1);
    }
    if(mid < r){
        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 if(segtree[p].f != -INF || segtree[p].s != INF){
        push((p<<1),segtree[p]); push((p<<1)|1,segtree[p]);
        segtree[p].f = -INF; segtree[p].s = INF;
    }
    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
0 / 8.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 348 KB Output is correct
4 Incorrect 4 ms 2868 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 81 ms 14012 KB Output is correct
3 Correct 144 ms 9812 KB Output is correct
4 Incorrect 373 ms 20564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
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 348 KB Output is correct
4 Incorrect 5 ms 2904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Incorrect 5 ms 2908 KB Output isn't correct
5 Halted 0 ms 0 KB -