# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
205079 |
2020-02-27T20:48:49 Z |
awlintqaa |
Wall (IOI14_wall) |
C++14 |
|
1275 ms |
16632 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[6000009];
struct xxx{int on,mx,mn;}lzy[600009];
void fill(int past,int cur){
if(lzy[cur].on==0){
lzy[cur]=lzy[past];
return ;
}
int x=lzy[past].mn;
if(x>lzy[cur].mn)
lzy[cur].mn=x;
if(x>lzy[cur].mx)
lzy[cur].mx=x;
x=lzy[past].mx;
if(x<lzy[cur].mn)
lzy[cur].mn=x;
if(x<lzy[cur].mx)
lzy[cur].mx=x;
}
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 |
376 KB |
Output is correct |
2 |
Correct |
6 ms |
380 KB |
Output is correct |
3 |
Correct |
7 ms |
376 KB |
Output is correct |
4 |
Correct |
15 ms |
1016 KB |
Output is correct |
5 |
Correct |
11 ms |
1016 KB |
Output is correct |
6 |
Correct |
11 ms |
1016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
194 ms |
8188 KB |
Output is correct |
3 |
Correct |
372 ms |
4720 KB |
Output is correct |
4 |
Correct |
1205 ms |
12984 KB |
Output is correct |
5 |
Correct |
364 ms |
13432 KB |
Output is correct |
6 |
Correct |
370 ms |
13420 KB |
Output is correct |
# |
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 |
Correct |
7 ms |
376 KB |
Output is correct |
4 |
Correct |
17 ms |
1016 KB |
Output is correct |
5 |
Correct |
11 ms |
1016 KB |
Output is correct |
6 |
Correct |
12 ms |
1016 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
188 ms |
8188 KB |
Output is correct |
9 |
Correct |
390 ms |
4728 KB |
Output is correct |
10 |
Correct |
1199 ms |
12920 KB |
Output is correct |
11 |
Correct |
377 ms |
13432 KB |
Output is correct |
12 |
Correct |
360 ms |
13360 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
190 ms |
8184 KB |
Output is correct |
15 |
Correct |
74 ms |
2028 KB |
Output is correct |
16 |
Correct |
1275 ms |
13132 KB |
Output is correct |
17 |
Correct |
364 ms |
13176 KB |
Output is correct |
18 |
Correct |
369 ms |
13180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
7 ms |
376 KB |
Output is correct |
3 |
Correct |
7 ms |
376 KB |
Output is correct |
4 |
Correct |
15 ms |
1016 KB |
Output is correct |
5 |
Correct |
11 ms |
1016 KB |
Output is correct |
6 |
Correct |
15 ms |
1020 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
185 ms |
8188 KB |
Output is correct |
9 |
Correct |
373 ms |
4856 KB |
Output is correct |
10 |
Correct |
1153 ms |
12844 KB |
Output is correct |
11 |
Correct |
355 ms |
13436 KB |
Output is correct |
12 |
Correct |
351 ms |
13432 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
183 ms |
8312 KB |
Output is correct |
15 |
Correct |
62 ms |
2040 KB |
Output is correct |
16 |
Correct |
1166 ms |
13124 KB |
Output is correct |
17 |
Correct |
358 ms |
13176 KB |
Output is correct |
18 |
Correct |
353 ms |
13308 KB |
Output is correct |
19 |
Runtime error |
228 ms |
16632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
20 |
Halted |
0 ms |
0 KB |
- |