oj.uz

Submission #823969

# Submission time Handle Problem Language Result Execution time Memory
823969 2023-08-13T10:50:59 Z annabeth9680 Wall (IOI14_wall) C++17
0 / 100
 121 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF = 2000000011;
const pair<int,int> def = make_pair(-INF,INF);
pair<int,int> tree[8000000]; //first is the add part, second remove
int N, Q; 
void build(int curl = 0, int curr = N-1, int p = 1){
    if(curl == 0 && curr == N-1){
        tree[p] = make_pair(0,0); 
    }
    else{
        tree[p] = def;
    }
  	if(curl == curr) return; 
    int mid = (curl+curr)>>1;
    build(curl,mid,p<<1);
    build(mid+1,curr,p<<1|1);
}
pair<int,int> comb(pair<int,int> a, pair<int,int> b){ //change b using a's info
    if(a.second < b.first){
        return make_pair(a.second,a.second);
    }
    if(a.first > b.second){
        return make_pair(a.first,a.first);
    }
    return make_pair(max(a.first,b.first),min(a.second,b.second));
}
void push(int p){
    if(tree[p] != def){
        tree[p<<1] = comb(tree[p],tree[p<<1]);
        tree[p<<1|1] = comb(tree[p],tree[p<<1|1]);
        tree[p] = def;
    }
}
void update(int curl, int curr, int p, int findl, int findr, pair<int,int> val){
    if(findr < curl || curr < findl) return;
    if(findl < curl && curr < findr){
        tree[p] = comb(val,tree[p]);
        return;
    }
    if(curl != curr) push(p);
    int mid = (curl+curr)>>1;
    update(curl,mid,(p<<1),findl,findr,val);
    update(mid+1,curr,p<<1|1,findl,findr,val);
}
void query(int* ans, int p, int curl, int curr){
    if(curl == curr){
        ans[p] = tree[p].first;
        return;
    }
    push(p);
    int mid = (curl+curr)>>1;
    query(ans,p<<1,curl,mid);
    query(ans,p<<1|1,mid+1,curr);
}
void buildWall(int n, int k, int* op, int* lb, int* rb, int* h, int* ans){
    N = n; Q = k; 
    build();
    for(int q = 0;q<Q;++q){
        pair<int,int> val = def;
        if(op[q] == 1) val.first = h[q];
        else val.second = h[q];
        update(0,N-1,1,lb[q],rb[q],val);
    }
    query(ans,1,0,N-1);
}
int n, q,op[500005], lb[500005], rb[500005], h[500005], ans[500005];

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 102 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 102 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -