#include <bits/stdc++.h>
using namespace std;
struct node{
int s,e;
int minv,maxv;
node *l,*r;
node (int _s, int _e){
s = _s; e = _e;
if (s!=e){
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
}
minv = 999999999;
maxv = -1;
}
void upd(int pos, int val){
minv = min(minv,val);
maxv = max(maxv,val);
if (s==e) return;
if (pos<=(s+e)/2) l->upd(pos,val);
else r->upd(pos,val);
}
int querymin(int a, int b){
if (a<=s && e<=b){
return minv;
}
else if (b<=(s+e)/2) return l->querymin(a,b);
else if (a>(s+e)/2) return r->querymin(a,b);
else return min(l->querymin(a,b),r->querymin(a,b));
}
int querymax(int a, int b){
if (a<=s && e<=b){
return maxv;
}
else if (b<=(s+e)/2) return l->querymax(a,b);
else if (a>(s+e)/2) return r->querymax(a,b);
else return max(l->querymax(a,b),r->querymax(a,b));
}
int rightblock(int minpos, int val){
// printf("call rightblock %d %d on %d %d\n",minpos,val,s,e);
if (s==e){
return minv<val?s:999999999;
}
if (minpos==s){
if (l->minv<val) return l->rightblock(minpos,val);
else return r->rightblock((s+e)/2+1,val);
}
if (minpos>(s+e)/2){
return r->rightblock(minpos,val);
}
int t = l->rightblock(minpos,val);
if (t==999999999){
return r->rightblock((s+e)/2+1,val);
}
else return t;
}
int leftblock(int maxpos, int val){
if (s==e){
return maxv>val?s:-1;
}
if (maxpos==e){
if (r->maxv>val) return r->leftblock(maxpos,val);
else return l->leftblock(maxpos,val);
}
if (maxpos<=(s+e)/2) return l->leftblock(maxpos,val);
int t = r->leftblock(maxpos,val);
if (t==-1) return l->leftblock(maxpos,val);
else return t;
}
}*root1,*root2;
int walltype[500005];
vector<int> keys[500005];
int intervall[500005];
int intervalr[500005];
int walll[500005];
int wallr[500005];
unordered_map<int,int> tempmap;
void rec(int l, int r, vector<int> &thing){
vector<pair<int,int> > stuff;
for (int x = l; x<=r; x++){
stuff.push_back({-(x&-x),x});
}
sort(stuff.begin(),stuff.end());
for (auto x : stuff){
thing.push_back(x.second);
}
}
int main(){
assert(false);
int n;
scanf("%d",&n);
root1 = new node(0,n+1);
root2 = new node(0,n+1);
for (int x = 1; x<n; x++){
scanf("%d",&walltype[x]);
}
for (int x = 1; x<=n; x++){
int t;
scanf("%d",&t);
for (int y = 0; y<t; y++){
int a;
scanf("%d",&a);
keys[x].push_back(a);
}
}
for (int x = 1; x<n; x++){
for (auto y : keys[x]){
tempmap[y] = x;
}
if (tempmap.count(walltype[x])) walll[x] = tempmap[walltype[x]];
else walll[x] = 0;
}
tempmap.clear();
for (int x = n-1; x>0; x--){
for (auto y : keys[x+1]){
tempmap[y] = x+1;
}
if (tempmap.count(walltype[x])) wallr[x] = tempmap[walltype[x]];
else wallr[x] = n+1;
}
for (int x = 1; x<n; x++){
root1->upd(x,walll[x]);
root1->upd(x,wallr[x]);
}
vector<int> order;
rec(1,n,order);
// printf("wall preproc done\n");
int num_iter = 0;
for (int x : order){
int curl = x;
int curr = x;
while (true){
// printf("curl,curr = %d %d\n",curl,curr);
num_iter++;
assert(num_iter<5*n);
int newr = root1->rightblock(curr,curl);
newr = min(newr,n);
// printf("rightblock %d %d = %d\n",curr,curl,newr);
int newl = root1->leftblock(curl-1,newr)+1;
newl = max(newl,1);
//printf("leftblock %d %d = %d\n",curl-1,curr,newl);
if (newl==curl&& newr==curr) {
intervall[x] = curl;
intervalr[x] = curr;
break;
}
if (newl<curl){
int te = root2->querymax(newl,x-1);
if (te>=x){
intervalr[x] = te;
intervall[x] = root2->querymin(newl,x-1);
break;
}
}
if (newr>curr){
int te = root2->querymin(x+1,newr);
if (te<=x){
intervall[x] = te;
intervalr[x] = root2->querymax(x+1,newr);
break;
}
}
curl = newl;
curr = newr;
}
root2->upd(x,intervalr[x]);
root2->upd(x,intervall[x]);
// printf("interval[%d] = %d %d\n",x,intervall[x],intervalr[x]);
}
int q;
scanf("%d",&q);
for (int x = 0; x<q; x++){
int a,b;
scanf("%d%d",&a,&b);
if (b<=intervalr[a] && b>=intervall[a]){
printf("YES\n");
}
else{
printf("NO\n");
}
}
}
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
long_mansion.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf("%d",&walltype[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~~
long_mansion.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d",&t);
| ~~~~~^~~~~~~~~
long_mansion.cpp:109:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | scanf("%d",&a);
| ~~~~~^~~~~~~~~
long_mansion.cpp:178:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
178 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
long_mansion.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
181 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
24268 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
24268 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
24208 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
24268 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
