# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
205209 |
2020-02-28T10:06:28 Z |
awlintqaa |
Wall (IOI14_wall) |
C++14 |
|
950 ms |
13560 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"
int tree[8000009];
struct xxx{int on,mx,mn;}lzy[800009];
void fill(int pre,int node){
if(lzy[node].on==0){
lzy[node]=lzy[pre];
return ;
}
lzy[node].mn=max(lzy[node].mn,lzy[pre].mn);
lzy[node].mx=min(lzy[node].mx,lzy[pre].mx);
}
void lzyUPD(int node,int l,int r){
if(lzy[node].on==0)return;
tree[node]=max(tree[node],lzy[node].mn);
tree[node]=min(tree[node],lzy[node].mx);
if(l!=r){
fill(node,node*2);
fill(node,node*2+1);
}
lzy[node].on=0;
lzy[node].mn=-inf;
lzy[node].mx=inf;
}
void upd(int node,int l,int r,int s,int e,int val,int t){
lzyUPD(node,l,r);
if(s>r || e<l)return ;
if(s<=l && e>=r){
if(t==1)lzy[node].mn=val,lzy[node].mx=inf;
else lzy[node].mn=-inf,lzy[node].mx=val;
lzy[node].on=1;
lzyUPD(node,l,r);
return ;
}
upd(node*2,l,mid,s,e,val,t);
upd(node*2+1,mid+1,r,s,e,val,t);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node,int l,int r,int id){
lzyUPD(node,l,r);
if(l==r)return tree[node];
if(id<=mid)return query(node*2,l,mid,id);
return query(node*2+1,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(1,0,n-1,left[i],right[i],height[i],op[i]);
for(int i=0;i<n;i++)finalHeight[i]=query(1,0,n-1,i);
}
# |
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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
182 ms |
8180 KB |
Output is correct |
3 |
Correct |
308 ms |
4728 KB |
Output is correct |
4 |
Correct |
950 ms |
13048 KB |
Output is correct |
5 |
Correct |
352 ms |
13560 KB |
Output is correct |
6 |
Correct |
345 ms |
13432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 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 |
- |
# |
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 |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |