Submission #205225

#	Time	Username	Problem	Language	Result	Execution time	Memory
205225		awlintqaa	Wall (IOI14_wall)	C++14	0 / 100	352 ms	8184 KiB

wall

#include <bits/stdc++.h>
using namespace std;
#define sqr 200
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1e9+7;
const ll inf= 2e9;
const ld pai=acos(-1);
#include "wall.h"
struct NODE{
        int tree,on,mn,mx;
        NODE *left,*right;
        NODE(){
                tree=on=0;
                mn=-inf,mx=inf;
                left=right=NULL;
        }
}*root=new NODE;
void fill(NODE *pre,NODE *node){
        if(node->on==0){
                node->on=pre->on;
                node->mn=pre->mn;
                node->mx=pre->mx;
                return ;
        }
        node->mn=max(node->mn,pre->mn);
        node->mx=max(node->mx,pre->mx);
        node->mx=min(node->mx,pre->mx);
        node->mn=min(node->mn,pre->mx);
}
void lzyUPD(NODE *node){
        if(node->on==0)return ;
        node->tree=max(node->tree,node->mn);
        node->tree=min(node->tree,node->mx);
        if(node->left==NULL)node->left=new NODE;
        if(node->right==NULL)node->right=new NODE;
        fill(node,node->left);
        fill(node,node->right);
        node->on=0;
        node->mn=-inf;
        node->mx=inf;
}
void upd(NODE *node,int l,int r,int s,int e,int x,int t){;
        lzyUPD(node);
        if(s<=l && e>=r){
                if(t==1)node->mn=x;
                if(t==2)node->mx=x;
                node->on=1;
                lzyUPD(node);
                return ;
        }
        if(s<=mid){
                if(node->left==NULL)node->left=new NODE;
                upd(node->left,l,mid,s,e,x,t);
        }
        if(e>=mid+1){
                if(node->right==NULL)node->right=new NODE;
                upd(node->right,mid+1,r,s,e,x,t);
        }
        int ret=-inf;
        if(node->left!=NULL){
                lzyUPD(node->left);
                ret=max(ret,node->left->tree);
        }
        if(node->right!=NULL){
                lzyUPD(node->right);
                ret=max(ret,node->right->tree);
        }
        node->tree=ret;
}
int query(NODE *node,int l,int r,int id){
        lzyUPD(node);
        if(l==r)return node->tree;
        if(id<=mid){
                if(node->left==NULL)return 0;
                return query(node->left,l,mid,id);
        }
        if(node->right==NULL)return 0;
        return query(node->right,mid+1,r,id);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
        for(int i=0;i<k;i++)upd(root,0,n-1,left[i],right[i],height[i],op[i]);
        for(int i=0;i<n;i++)finalHeight[i]=query(root,0,n-1,i);
}

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