#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];
map<int,int> tempmap;
int main(){
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;
}
walll[x] = tempmap[walltype[x]];
}
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]);
}
// printf("wall preproc done\n");
for (int x = 1; x<=n; x++){
int curl = x;
int curr = x;
while (true){
printf("curl,curr = %d %d\n",curl,curr);
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;
}
}
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:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
long_mansion.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%d",&walltype[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~~
long_mansion.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d",&t);
| ~~~~~^~~~~~~~~
long_mansion.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d",&a);
| ~~~~~^~~~~~~~~
long_mansion.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
long_mansion.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
155 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3051 ms |
40404 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
