This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define F first
#define S second
#define mp make_pair
#define pb push_back
using namespace std;
const int mxn = 1e7 , N =2e6+500 ;
vector<vector<int>> sg(2,vector<int>(mxn,-1));
int query(int t ,int in,int l ,int r ,int ql ,int qr){
if(qr<l||r<ql) return -1 ;
if(ql<=l&&r<=qr) return sg[t][in] ;
int ans = query(t,in*2,l,(r+l)/2,ql,qr);
ans=max(ans,query(t,in*2+1,(r+l)/2+1,r,ql,qr)) ;
return ans;
}
int query(int i ,int t){
if(t) i=N-i;
return query(t,1,0,N,0,i);
}
void update(int t , int in, int l ,int r , int i,int v){
if(i<l||r<i) return ;
if(l==i&&r==i){
sg[t][in]=v ;
return ;
}
update(t,in*2,l,(r+l)/2,i,v);
update(t,in*2+1,(l+r)/2+1,r,i,v);
sg[t][in]=max(sg[t][in*2],sg[t][in*2+1]) ;
//return sg[t][in] ;
}
void update(int i , int v , int t){
if(t) i=N-i;
update(t,1,0,N,i,v) ;
return ;
}
void buildWall(int n,int k,int op[],int le[],int re[],int he[],int* ans){
vector<vector<array<int,3>>> in(n) , out(n);
set<int> ok ;
for(int i=0;i<k;i++){
if(op[i]==2) op[i]=0;
}
for(int i=0;i<k;i++) ok.insert(he[i]) ;
ok.insert(0);
int cnt =1;
map<int,int> ki ,rk ;
for(int x:ok) ki[x]=++cnt,rk[cnt]=x;
for(int i=0;i<k;i++){
in[le[i]].pb({op[i],ki[he[i]],i}) ;
out[re[i]].pb({op[i],ki[he[i]],i});
}
set<int> hey[2][cnt+1];
for(int i=0;i<n;i++){
for(auto x : in[i]){
int t = x[0] , he = x[1],tim=x[2] ;
hey[t][he].insert(tim) ;
tim = *(--hey[t][he].end()) ;
update(he,tim,t) ;
}
int l=1,r=cnt+1;
while(r-l!=1){
int md=(r+l)/2 ;
int val = query(0,1,0,N,0,md-1) ,vall = query(1,1,0,N,0,N-md);
if(vall>val) l=md ;
else r=md;
}
ans[i]=rk[l];
for(auto x: out[i]){
int t=x[0],he=x[1],tim=x[2];
hey[t][he].erase(tim) ;
update(he,-1,t);
if(hey[t][he].size()){
update(he,*(--hey[t][he].end()),t);
}
}
}
return ;
}
Compilation message (stderr)
wall.cpp:7:1: error: 'vector' does not name a type
7 | vector<vector<int>> sg(2,vector<int>(mxn,-1));
| ^~~~~~
wall.cpp: In function 'int query(int, int, int, int, int, int)':
wall.cpp:10:29: error: 'sg' was not declared in this scope
10 | if(ql<=l&&r<=qr) return sg[t][in] ;
| ^~
wall.cpp:12:9: error: 'max' was not declared in this scope
12 | ans=max(ans,query(t,in*2+1,(r+l)/2+1,r,ql,qr)) ;
| ^~~
wall.cpp: In function 'void update(int, int, int, int, int, int)':
wall.cpp:22:9: error: 'sg' was not declared in this scope
22 | sg[t][in]=v ;
| ^~
wall.cpp:27:5: error: 'sg' was not declared in this scope
27 | sg[t][in]=max(sg[t][in*2],sg[t][in*2+1]) ;
| ^~
wall.cpp:27:15: error: 'max' was not declared in this scope
27 | sg[t][in]=max(sg[t][in*2],sg[t][in*2+1]) ;
| ^~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:36:5: error: 'vector' was not declared in this scope
36 | vector<vector<array<int,3>>> in(n) , out(n);
| ^~~~~~
wall.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
+++ |+#include <vector>
1 | #define F first
wall.cpp:36:19: error: 'array' was not declared in this scope
36 | vector<vector<array<int,3>>> in(n) , out(n);
| ^~~~~
wall.cpp:1:1: note: 'std::array' is defined in header '<array>'; did you forget to '#include <array>'?
+++ |+#include <array>
1 | #define F first
wall.cpp:36:25: error: expected primary-expression before 'int'
36 | vector<vector<array<int,3>>> in(n) , out(n);
| ^~~
wall.cpp:37:5: error: 'set' was not declared in this scope
37 | set<int> ok ;
| ^~~
wall.cpp:1:1: note: 'std::set' is defined in header '<set>'; did you forget to '#include <set>'?
+++ |+#include <set>
1 | #define F first
wall.cpp:37:9: error: expected primary-expression before 'int'
37 | set<int> ok ;
| ^~~
wall.cpp:41:26: error: 'ok' was not declared in this scope; did you mean 'k'?
41 | for(int i=0;i<k;i++) ok.insert(he[i]) ;
| ^~
| k
wall.cpp:42:5: error: 'ok' was not declared in this scope; did you mean 'k'?
42 | ok.insert(0);
| ^~
| k
wall.cpp:44:5: error: 'map' was not declared in this scope
44 | map<int,int> ki ,rk ;
| ^~~
wall.cpp:1:1: note: 'std::map' is defined in header '<map>'; did you forget to '#include <map>'?
+++ |+#include <map>
1 | #define F first
wall.cpp:44:9: error: expected primary-expression before 'int'
44 | map<int,int> ki ,rk ;
| ^~~
wall.cpp:45:19: error: 'ki' was not declared in this scope; did you mean 'k'?
45 | for(int x:ok) ki[x]=++cnt,rk[cnt]=x;
| ^~
| k
wall.cpp:45:31: error: 'rk' was not declared in this scope; did you mean 'k'?
45 | for(int x:ok) ki[x]=++cnt,rk[cnt]=x;
| ^~
| k
wall.cpp:47:9: error: 'in' was not declared in this scope; did you mean 'i'?
47 | in[le[i]].pb({op[i],ki[he[i]],i}) ;
| ^~
| i
wall.cpp:47:29: error: 'ki' was not declared in this scope; did you mean 'i'?
47 | in[le[i]].pb({op[i],ki[he[i]],i}) ;
| ^~
| i
wall.cpp:48:9: error: 'out' was not declared in this scope
48 | out[re[i]].pb({op[i],ki[he[i]],i});
| ^~~
wall.cpp:50:9: error: expected primary-expression before 'int'
50 | set<int> hey[2][cnt+1];
| ^~~
wall.cpp:52:23: error: 'in' was not declared in this scope; did you mean 'i'?
52 | for(auto x : in[i]){
| ^~
| i
wall.cpp:54:13: error: 'hey' was not declared in this scope; did you mean 'he'?
54 | hey[t][he].insert(tim) ;
| ^~~
| he
wall.cpp:54:31: error: 'tim' was not declared in this scope
54 | hey[t][he].insert(tim) ;
| ^~~
wall.cpp:65:16: error: 'rk' was not declared in this scope; did you mean 'r'?
65 | ans[i]=rk[l];
| ^~
| r
wall.cpp:66:21: error: 'out' was not declared in this scope
66 | for(auto x: out[i]){
| ^~~
wall.cpp:68:13: error: 'hey' was not declared in this scope; did you mean 'he'?
68 | hey[t][he].erase(tim) ;
| ^~~
| he
wall.cpp:68:30: error: 'tim' was not declared in this scope
68 | hey[t][he].erase(tim) ;
| ^~~
wall.cpp:69:20: error: invalid conversion from 'int*' to 'int' [-fpermissive]
69 | update(he,-1,t);
| ^~
| |
| int*
wall.cpp:30:17: note: initializing argument 1 of 'void update(int, int, int)'
30 | void update(int i , int v , int t){
| ~~~~^