oj.uz

Submission #431606

# Submission time Handle Problem Language Result Execution time Memory
431606 2021-06-17T13:32:21 Z tqbfjotld Long Mansion (JOI17_long_mansion) C++14
25 / 100
 3000 ms 137072 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(maxpos,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 14 ms 12588 KB Output is correct
2 Correct 16 ms 12852 KB Output is correct
3 Correct 28 ms 13376 KB Output is correct
4 Correct 15 ms 12660 KB Output is correct
5 Correct 16 ms 12492 KB Output is correct
6 Correct 15 ms 12640 KB Output is correct
7 Correct 14 ms 12588 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12588 KB Output is correct
2 Correct 16 ms 12852 KB Output is correct
3 Correct 28 ms 13376 KB Output is correct
4 Correct 15 ms 12660 KB Output is correct
5 Correct 16 ms 12492 KB Output is correct
6 Correct 15 ms 12640 KB Output is correct
7 Correct 14 ms 12588 KB Output is correct
8 Correct 153 ms 14148 KB Output is correct
9 Correct 149 ms 14168 KB Output is correct
10 Correct 166 ms 14444 KB Output is correct
11 Correct 177 ms 15152 KB Output is correct
12 Correct 153 ms 13980 KB Output is correct
13 Correct 146 ms 14320 KB Output is correct
14 Correct 180 ms 14400 KB Output is correct
15 Correct 171 ms 14308 KB Output is correct
16 Correct 138 ms 14560 KB Output is correct
17 Correct 147 ms 14348 KB Output is correct
18 Correct 166 ms 14376 KB Output is correct
19 Correct 178 ms 14324 KB Output is correct
20 Correct 158 ms 14476 KB Output is correct
21 Correct 141 ms 14560 KB Output is correct
22 Correct 155 ms 14412 KB Output is correct
23 Correct 157 ms 14240 KB Output is correct
24 Correct 154 ms 14176 KB Output is correct
25 Correct 154 ms 14176 KB Output is correct
26 Correct 146 ms 14144 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 39228 KB Output is correct
2 Correct 832 ms 39092 KB Output is correct
3 Correct 1248 ms 39156 KB Output is correct
4 Correct 657 ms 39260 KB Output is correct
5 Correct 658 ms 39300 KB Output is correct
6 Correct 1067 ms 38768 KB Output is correct
7 Correct 2381 ms 38932 KB Output is correct
8 Correct 2504 ms 38920 KB Output is correct
9 Correct 2560 ms 38932 KB Output is correct
10 Correct 2676 ms 38908 KB Output is correct
11 Correct 2653 ms 38920 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12588 KB Output is correct
2 Correct 16 ms 12852 KB Output is correct
3 Correct 28 ms 13376 KB Output is correct
4 Correct 15 ms 12660 KB Output is correct
5 Correct 16 ms 12492 KB Output is correct
6 Correct 15 ms 12640 KB Output is correct
7 Correct 14 ms 12588 KB Output is correct
8 Correct 153 ms 14148 KB Output is correct
9 Correct 149 ms 14168 KB Output is correct
10 Correct 166 ms 14444 KB Output is correct
11 Correct 177 ms 15152 KB Output is correct
12 Correct 153 ms 13980 KB Output is correct
13 Correct 146 ms 14320 KB Output is correct
14 Correct 180 ms 14400 KB Output is correct
15 Correct 171 ms 14308 KB Output is correct
16 Correct 138 ms 14560 KB Output is correct
17 Correct 147 ms 14348 KB Output is correct
18 Correct 166 ms 14376 KB Output is correct
19 Correct 178 ms 14324 KB Output is correct
20 Correct 158 ms 14476 KB Output is correct
21 Correct 141 ms 14560 KB Output is correct
22 Correct 155 ms 14412 KB Output is correct
23 Correct 157 ms 14240 KB Output is correct
24 Correct 154 ms 14176 KB Output is correct
25 Correct 154 ms 14176 KB Output is correct
26 Correct 146 ms 14144 KB Output is correct
27 Correct 586 ms 39228 KB Output is correct
28 Correct 832 ms 39092 KB Output is correct
29 Correct 1248 ms 39156 KB Output is correct
30 Correct 657 ms 39260 KB Output is correct
31 Correct 658 ms 39300 KB Output is correct
32 Correct 1067 ms 38768 KB Output is correct
33 Correct 2381 ms 38932 KB Output is correct
34 Correct 2504 ms 38920 KB Output is correct
35 Correct 2560 ms 38932 KB Output is correct
36 Correct 2676 ms 38908 KB Output is correct
37 Correct 2653 ms 38920 KB Output is correct
38 Correct 1018 ms 113140 KB Output is correct
39 Correct 1062 ms 137072 KB Output is correct
40 Correct 834 ms 88616 KB Output is correct
41 Execution timed out 3054 ms 135504 KB Time limit exceeded
42 Halted 0 ms 0 KB -