Submission #852808

#	Time	Username	Problem	Language	Result	Execution time	Memory
852808		Samrev	Wall (IOI14_wall)	C++14	24 / 100	367 ms	21696 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define LSOne(x) (x&(-x))
typedef long long int ll;
typedef long double ld;
ll t = 1;
const ll M = 1e9 + 7;
ll mod_add(ll a, ll b){
    return ((a%M) + (b %M))%M;
}
ll mod_mul(ll a, ll b){
    return ((a%M)*(b%M))%M;
}
const ll MAX = 1e18;

ll lcm(ll a , ll b){
    return (a*b)/__gcd(a,b);
}
struct Node{
    int v, hadd,hremove;
};
struct  SegTree
{
    vector<Node> tree;
    int sz = 1;
    SegTree(int n){
        while(sz <= n){
            sz *=2;
        }
        tree.assign(2*sz , {0,0, INT_MAX});
    }
    void apply_op(int op , int h , int x){
        if(op == 1){
            tree[x].hadd = max(tree[x].hadd,h);
            if(tree[x].hadd > tree[x].hremove){
                tree[x].hremove = INT_MAX;
            }
        }
        else{
            tree[x].hremove = min(tree[x].hremove , h);
            if(tree[x].hremove < tree[x].hadd){
                tree[x].hadd = tree[x].hremove;
            }
        }
    }
    void push(int x , int lx ,int rx){
        
        if((rx - lx) == 1)  return;
        apply_op(2,tree[x].hremove,2*x + 1);
        apply_op(1,tree[x].hadd , 2*x + 1);
        
        apply_op(2 , tree[x].hremove , 2*x + 2);
        apply_op(1,tree[x].hadd,2*x + 2);
        
        tree[x] = {0,0,INT_MAX};
    }
    void update(int l , int r ,int op , int h , int x , int lx , int rx){
        if((lx>=r) || (rx<=l)) return;
        push(x,lx,rx);
        if((rx - lx) == 1){
            apply_op(op , h , x);
            return;
        }
        
        if((lx>=l) && (rx<=r)){
            apply_op(op ,h ,x);
            return;
        }
        int m = lx + (rx - lx)/2;
        update(l , r , op , h , 2*x + 1, lx , m);
        update(l , r , op , h , 2*x + 2, m , rx);
    }
    void update(int l , int r , int op , int h){
        return update(l , r, op , h , 0 , 0 , sz);
    }
    void get(int finalHeight[] , int i , int x,int lx,int rx){
        push(x,lx,rx);
        
        if((rx - lx) == 1){
            finalHeight[lx] = tree[x].hadd;
            return;
        }
        int m = lx + (rx - lx)/2;
        

        if(i<m){
            get(finalHeight,i , 2*x + 1, lx , m);
        }
        else{
            get(finalHeight,i , 2*x + 2, m , rx);
        }
    }
    void get(int finalHeight[], int i){
        return get(finalHeight,i , 0 , 0 , sz);
    }

};
void buildWall(int n, int k, int op[], int left[], int right[],
    int height[], int finalHeight[]){
    SegTree sg(n);
    for(int i = 0 ; i<k;i++){
        
        sg.update(left[i],right[i]+1,op[i],height[i]);
    }
    
    for(int i = 0 ; i<n ; i++){
        sg.get(finalHeight,i);
    }
}
// void solve(){
//     int n,k;cin>>n>>k;
//     int finalHeight[n],height[n],op[k],left[k],right[k];
//     for(int i  = 0 ; i<k ; i++){
//         cin>>op[i];
//     }
//     for(int i  = 0 ; i<k ; i++){
//         cin>>left[i];
//     }
//     for(int i  = 0 ; i<k ; i++){
//         cin>>right[i];
//     }
//     for(int i  = 0 ; i<n ; i++){
//         cin>>height[i];
//         finalHeight[i] = 0;
//     }
//     buildWall(n , k , op , left,right,height,finalHeight);
//     for(int i  = 0 ; i<n ; i++){
//         cout<<finalHeight[i]<<" ";
//     }
    
// }
    
    




// int main(){

//     ios::sync_with_stdio(0); cin.tie(0);
//     freopen("input.txt" , "r" , stdin);
//     freopen("output.txt" , "w", stdout);
//     // cin>>t;
//     while(t--){
//         solve();
//     }
// }

• Subtask 1: 0 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39