///~~~LOTA~~~///
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define LIMIT 50000001
#define MAXN 100000
int L[4*MAXN];
int R[4*MAXN];
int ANS[MAXN];
void get(int l=0,int r=MAXN,int v=1,int s=0,int e=MAXN){
l=max(l,L[v]);
r=min(r,R[v]);
if(e-s==1){
ANS[s]=min(l,r);
return;
}
int lc,rc,mid;
lc=2*v;
rc=2*v+1;
mid=(s+e)/2;
get(l,r,lc,s,mid);
get(l,r,rc,mid,e);
}
void update(int l,int r,int x,int i,int v=1,int s=0,int e=MAXN){
if(r<=s || e<=l || s>=e) return;
if(l<=s && e<=r){
if(i==1) L[v]=max(L[v],x);
else R[v]=min(R[v],x);
return;
}
int lc,rc,mid;
lc=2*v;
rc=2*v+1;
mid=(s+e)/2;
update(l,r,x,i,lc,s,mid);
update(l,r,x,i,rc,mid,e);
}
void buildWall(int n,int m,int t[],int l[],int r[],int h[],int ans[]){
for(int i=0;i<4*MAXN;i++)
R[i]=MAXN;
for(int i=0;i<m;i++){
if(n*m<LIMIT){
for(int j=l[i];j<=r[i];j++){
if(t[i]==1) ANS[j]=max(ANS[j],h[i]);
else ANS[j]=min(ANS[j],h[i]);
}
}
else update(l[i],r[i]+1,h[i],t[i]);
}
if(n*m>=LIMIT) get();
for(int i=0;i<n;i++) ans[i]=ANS[i];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
3 ms |
2504 KB |
Output is correct |
3 |
Correct |
2 ms |
2548 KB |
Output is correct |
4 |
Correct |
25 ms |
2728 KB |
Output is correct |
5 |
Correct |
17 ms |
2664 KB |
Output is correct |
6 |
Correct |
23 ms |
2664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2408 KB |
Output is correct |
2 |
Correct |
102 ms |
15968 KB |
Output is correct |
3 |
Correct |
1129 ms |
9652 KB |
Output is correct |
4 |
Execution timed out |
3083 ms |
20048 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
2 ms |
2628 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
16 ms |
2652 KB |
Output is correct |
5 |
Correct |
23 ms |
2652 KB |
Output is correct |
6 |
Correct |
19 ms |
2904 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
111 ms |
16064 KB |
Output is correct |
9 |
Correct |
1111 ms |
9644 KB |
Output is correct |
10 |
Execution timed out |
3096 ms |
20092 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
2 ms |
2396 KB |
Output is correct |
3 |
Correct |
2 ms |
2396 KB |
Output is correct |
4 |
Correct |
17 ms |
2648 KB |
Output is correct |
5 |
Correct |
16 ms |
2652 KB |
Output is correct |
6 |
Correct |
17 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
104 ms |
16012 KB |
Output is correct |
9 |
Correct |
1094 ms |
9648 KB |
Output is correct |
10 |
Execution timed out |
3007 ms |
20052 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |