oj.uz

Submission #122609

# Submission time Handle Problem Language Result Execution time Memory
122609 2019-06-28T18:02:11 Z brcode Wall (IOI14_wall) C++14
0 / 100
 228 ms 9976 KB 
#include <iostream>
#include "wall.h"
using namespace std;
struct node{
    int mn,mx;
};
const int MAXN = 4e6+5;
pair<int,int> lazy[4*MAXN];
int ans[MAXN];
int seg[4*MAXN];
void push(int curr,int l,int r){
    if(lazy[curr].first == -1e9 && lazy[curr].second == -1e9){
        return;
    }
    seg[curr] = max(seg[curr],lazy[curr].first);
    seg[curr] = min(seg[curr],lazy[curr].second);
    if(l!=r){
        auto a = lazy[2*curr];
        auto b = lazy[curr];
        if(b.second<=a.first){
            a = make_pair(b.second,b.second);
        }else if(b.first>=a.second){
            a = make_pair(b.first,b.first);
        }else{
            a.first = max(a.first,b.first);
            a.second = max(a.second,b.second);
        }
        lazy[2*curr] = a;
        a= lazy[2*curr+1];
        b = lazy[curr];
        if(b.second<=a.first){
            a = make_pair(b.second,b.second);
        }else if(b.first>=a.second){
            a = make_pair(b.first,b.first);
        }else{
            a.first = max(a.first,b.first);
            a.second = max(a.second,b.second);
        }
        lazy[2*curr+1] = a;
    }
    lazy[curr] = make_pair(-1e9,1e9);
}
void update(int curr,int l,int r,int tl,int tr,pair<int,int> p1){
    push(curr,l,r);
    if(l>tr||r<tl){
        return;
    }
    if(l>=tl && r<=tr){
        lazy[curr] = p1;
        push(curr,l,r);
        return;
    }
    int mid = (l+r)/2;
    update(2*curr,l,mid,tl,tr,p1);
    update(2*curr+1,mid+1,r,tl,tr,p1);
}
void solve(int curr,int l,int r){
    push(curr,l,r);
    if(l==r){
        ans[l-1] = seg[curr];
        return;
    }
    int mid = (l+r)/2;
    solve(2*curr,l,mid);
    solve(2*curr+1,mid+1,r);
    
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
    
   
    
    for(int i=0;i<k;i++){
        if(op[i] == 1){
            update(1,1,n,left[i]+1,right[i]+1,make_pair(height[i],1e9));
        }else{
            update(1,1,n,left[i]+1,right[i]+1,make_pair(-1e9,height[i]));
        }
        
    }
    solve(1,1,n);
    for(int i=0;i<n;i++){
        finalHeight[i] = ans[i];
        //cout<<i<<" "<<ans[i]<<endl;
    }
}
/*int main(){
    int n,k;
    cin>>n>>k;
    int left[k+1];
    int right[k+1];
    int height[k+1];
    int type[k+1];
    int finalHeight[k+1];
    for(int i=0;i<k;i++){
        cin>>type[i]>>left[i]>>right[i]>>height[i];
    }
    buildWall(n,k,type,left,right,height,finalHeight);
}*/

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 146 ms 9976 KB Output is correct
3 Incorrect 228 ms 6452 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

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