Submission #431593

#	Time	Username	Problem	Language	Result	Execution time	Memory
431593		tqbfjotld	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	3018 ms	37560 KiB

long_mansion

#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;

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(){
    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]);
    }
    vector<int> order;
    rec(1,n,order);
   // printf("wall preproc done\n");
    for (int x : order){
        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;
                }
            }
            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 (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         scanf("%d",&walltype[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
long_mansion.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
long_mansion.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |             scanf("%d",&a);
      |             ~~~~~^~~~~~~~~
long_mansion.cpp:173:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75