oj.uz

Submission #431609

# Submission time Handle Problem Language Result Execution time Memory
431609 2021-06-17T13:33:51 Z tqbfjotld Long Mansion (JOI17_long_mansion) C++14
100 / 100
 1381 ms 137100 KB 
#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((s+e)/2,val);
        }
        if (maxpos<=(s+e)/2) return l->leftblock(maxpos,val);
        int t = r->leftblock(maxpos,val);
        if (t==-1) return l->leftblock((s+e)/2,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(){
    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: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:177:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:180:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12528 KB Output is correct
2 Correct 16 ms 12748 KB Output is correct
3 Correct 20 ms 13320 KB Output is correct
4 Correct 17 ms 12620 KB Output is correct
5 Correct 17 ms 12492 KB Output is correct
6 Correct 14 ms 12620 KB Output is correct
7 Correct 15 ms 12652 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12528 KB Output is correct
2 Correct 16 ms 12748 KB Output is correct
3 Correct 20 ms 13320 KB Output is correct
4 Correct 17 ms 12620 KB Output is correct
5 Correct 17 ms 12492 KB Output is correct
6 Correct 14 ms 12620 KB Output is correct
7 Correct 15 ms 12652 KB Output is correct
8 Correct 196 ms 14084 KB Output is correct
9 Correct 144 ms 14064 KB Output is correct
10 Correct 172 ms 14408 KB Output is correct
11 Correct 158 ms 15264 KB Output is correct
12 Correct 170 ms 13980 KB Output is correct
13 Correct 151 ms 14252 KB Output is correct
14 Correct 151 ms 14284 KB Output is correct
15 Correct 138 ms 14316 KB Output is correct
16 Correct 141 ms 14560 KB Output is correct
17 Correct 143 ms 14276 KB Output is correct
18 Correct 141 ms 14384 KB Output is correct
19 Correct 155 ms 14312 KB Output is correct
20 Correct 145 ms 14444 KB Output is correct
21 Correct 140 ms 14484 KB Output is correct
22 Correct 145 ms 14324 KB Output is correct
23 Correct 156 ms 14252 KB Output is correct
24 Correct 163 ms 14148 KB Output is correct
25 Correct 142 ms 14148 KB Output is correct
26 Correct 166 ms 14116 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 39068 KB Output is correct
2 Correct 390 ms 39072 KB Output is correct
3 Correct 409 ms 39040 KB Output is correct
4 Correct 421 ms 39144 KB Output is correct
5 Correct 458 ms 39100 KB Output is correct
6 Correct 391 ms 38596 KB Output is correct
7 Correct 494 ms 38780 KB Output is correct
8 Correct 447 ms 38864 KB Output is correct
9 Correct 428 ms 38736 KB Output is correct
10 Correct 449 ms 38780 KB Output is correct
11 Correct 439 ms 38840 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12528 KB Output is correct
2 Correct 16 ms 12748 KB Output is correct
3 Correct 20 ms 13320 KB Output is correct
4 Correct 17 ms 12620 KB Output is correct
5 Correct 17 ms 12492 KB Output is correct
6 Correct 14 ms 12620 KB Output is correct
7 Correct 15 ms 12652 KB Output is correct
8 Correct 196 ms 14084 KB Output is correct
9 Correct 144 ms 14064 KB Output is correct
10 Correct 172 ms 14408 KB Output is correct
11 Correct 158 ms 15264 KB Output is correct
12 Correct 170 ms 13980 KB Output is correct
13 Correct 151 ms 14252 KB Output is correct
14 Correct 151 ms 14284 KB Output is correct
15 Correct 138 ms 14316 KB Output is correct
16 Correct 141 ms 14560 KB Output is correct
17 Correct 143 ms 14276 KB Output is correct
18 Correct 141 ms 14384 KB Output is correct
19 Correct 155 ms 14312 KB Output is correct
20 Correct 145 ms 14444 KB Output is correct
21 Correct 140 ms 14484 KB Output is correct
22 Correct 145 ms 14324 KB Output is correct
23 Correct 156 ms 14252 KB Output is correct
24 Correct 163 ms 14148 KB Output is correct
25 Correct 142 ms 14148 KB Output is correct
26 Correct 166 ms 14116 KB Output is correct
27 Correct 395 ms 39068 KB Output is correct
28 Correct 390 ms 39072 KB Output is correct
29 Correct 409 ms 39040 KB Output is correct
30 Correct 421 ms 39144 KB Output is correct
31 Correct 458 ms 39100 KB Output is correct
32 Correct 391 ms 38596 KB Output is correct
33 Correct 494 ms 38780 KB Output is correct
34 Correct 447 ms 38864 KB Output is correct
35 Correct 428 ms 38736 KB Output is correct
36 Correct 449 ms 38780 KB Output is correct
37 Correct 439 ms 38840 KB Output is correct
38 Correct 908 ms 113060 KB Output is correct
39 Correct 1026 ms 136944 KB Output is correct
40 Correct 688 ms 88528 KB Output is correct
41 Correct 1381 ms 137100 KB Output is correct
42 Correct 385 ms 40796 KB Output is correct
43 Correct 375 ms 39680 KB Output is correct
44 Correct 629 ms 67648 KB Output is correct
45 Correct 710 ms 67996 KB Output is correct
46 Correct 750 ms 68472 KB Output is correct
47 Correct 476 ms 40960 KB Output is correct
48 Correct 454 ms 39292 KB Output is correct
49 Correct 720 ms 65160 KB Output is correct
50 Correct 765 ms 66536 KB Output is correct
51 Correct 866 ms 68904 KB Output is correct
52 Correct 597 ms 72024 KB Output is correct
53 Correct 859 ms 99628 KB Output is correct
54 Correct 1022 ms 130928 KB Output is correct
55 Correct 797 ms 100248 KB Output is correct