# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
205225 |
2020-02-28T10:41:20 Z |
awlintqaa |
Wall (IOI14_wall) |
C++14 |
|
352 ms |
8184 KB |
#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);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
376 KB |
Output is correct |
3 |
Incorrect |
7 ms |
380 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
194 ms |
8184 KB |
Output is correct |
3 |
Incorrect |
352 ms |
7160 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
8 ms |
376 KB |
Output is correct |
3 |
Incorrect |
6 ms |
380 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
6 ms |
376 KB |
Output is correct |
3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |