oj.uz

Submission #533350

# Submission time Handle Problem Language Result Execution time Memory
533350 2022-03-05T15:31:17 Z couplefire Long Mansion (JOI17_long_mansion) C++17
100 / 100
 1721 ms 56468 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MN = 5e5+5;
int N, Q, t, i, x, y, l[MN], r[MN], c[MN], pre[MN], suf[MN], st[3*MN], lst[MN];
vector<int> a[MN];
 
void build(int i,int s,int e){
    if(s!=e){
        build(2*i,s,(s+e)/2);
        build(2*i+1,(s+e)/2+1,e);
        st[i]=min(st[2*i],st[2*i+1]);
    }
    else st[i]=pre[s];
}
 
int qu(int i,int s,int e,int ss,int se){
    if(s>=ss&&e<=se) return st[i];
    else if((s+e)/2<ss) return qu(2*i+1,(s+e)/2+1,e,ss,se);
    else if((s+e)/2>=se) return qu(2*i,s,(s+e)/2,ss,se);
    else return min(qu(2*i,s,(s+e)/2,ss,se),qu(2*i+1,(s+e)/2+1,e,ss,se));
}
 
int main(){
    for(scanf("%d",&N),i=1;i<N;i++) scanf("%d",&c[i]);
    for(i=1;i<=N;i++){
        scanf("%d",&t);
        while(t--) scanf("%d",&x), a[i].push_back(x);
    }
    for(i=1;i<N;i++){
        for(auto v : a[i]) lst[v]=i;
        pre[i]=lst[c[i]];
    }
    memset(lst,0,sizeof(lst));
    for(i=N;i>1;i--){
        for(auto v : a[i]) lst[v]=i;
        suf[i-1]=lst[c[i-1]];
    }
    build(1,1,N-1);
    for(i=1;i<=N;i++){
        int L=i, R=i;
        while(1){
            if(L>1&&suf[L-1]&&R>=suf[L-1]){
                R = max(R, r[L-1]);
                L = l[L-1];
            }
            else{
                int lo = R, hi = N;
                while(lo<hi){
                    int m = (lo+hi)/2;
                    if(qu(1,1,N-1,R,m)>=L) lo=m+1;
                    else hi=m;
                }
                if(lo==R) break;
                else R=lo;
            }
        }
        l[i]=L, r[i]=R;
    }
    for(scanf("%d",&Q);Q;Q--){
        scanf("%d%d",&x,&y);
        printf("%s\n",(r[x]>=y&&l[x]<=y)?"YES":"NO");
    }
    return 0;
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     for(scanf("%d",&N),i=1;i<N;i++) scanf("%d",&c[i]);
      |         ~~~~~^~~~~~~~~
long_mansion.cpp:25:42: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     for(scanf("%d",&N),i=1;i<N;i++) scanf("%d",&c[i]);
      |                                     ~~~~~^~~~~~~~~~~~
long_mansion.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
long_mansion.cpp:28:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         while(t--) scanf("%d",&x), a[i].push_back(x);
      |                    ~~~~~^~~~~~~~~
long_mansion.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     for(scanf("%d",&Q);Q;Q--){
      |         ~~~~~^~~~~~~~~
long_mansion.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14152 KB Output is correct
2 Correct 14 ms 14304 KB Output is correct
3 Correct 15 ms 14348 KB Output is correct
4 Correct 11 ms 14160 KB Output is correct
5 Correct 10 ms 14180 KB Output is correct
6 Correct 13 ms 14236 KB Output is correct
7 Correct 11 ms 14248 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14152 KB Output is correct
2 Correct 14 ms 14304 KB Output is correct
3 Correct 15 ms 14348 KB Output is correct
4 Correct 11 ms 14160 KB Output is correct
5 Correct 10 ms 14180 KB Output is correct
6 Correct 13 ms 14236 KB Output is correct
7 Correct 11 ms 14248 KB Output is correct
8 Correct 182 ms 20028 KB Output is correct
9 Correct 144 ms 19920 KB Output is correct
10 Correct 149 ms 20424 KB Output is correct
11 Correct 173 ms 20776 KB Output is correct
12 Correct 138 ms 19656 KB Output is correct
13 Correct 143 ms 20232 KB Output is correct
14 Correct 143 ms 20260 KB Output is correct
15 Correct 178 ms 20236 KB Output is correct
16 Correct 129 ms 19996 KB Output is correct
17 Correct 153 ms 20160 KB Output is correct
18 Correct 166 ms 20276 KB Output is correct
19 Correct 154 ms 20352 KB Output is correct
20 Correct 162 ms 20172 KB Output is correct
21 Correct 135 ms 19996 KB Output is correct
22 Correct 192 ms 20084 KB Output is correct
23 Correct 138 ms 19992 KB Output is correct
24 Correct 140 ms 19920 KB Output is correct
25 Correct 172 ms 19912 KB Output is correct
26 Correct 141 ms 19928 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 29776 KB Output is correct
2 Correct 437 ms 29588 KB Output is correct
3 Correct 405 ms 29304 KB Output is correct
4 Correct 522 ms 29600 KB Output is correct
5 Correct 440 ms 29648 KB Output is correct
6 Correct 361 ms 28376 KB Output is correct
7 Correct 214 ms 28140 KB Output is correct
8 Correct 215 ms 28092 KB Output is correct
9 Correct 211 ms 28156 KB Output is correct
10 Correct 247 ms 28144 KB Output is correct
11 Correct 189 ms 28088 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14152 KB Output is correct
2 Correct 14 ms 14304 KB Output is correct
3 Correct 15 ms 14348 KB Output is correct
4 Correct 11 ms 14160 KB Output is correct
5 Correct 10 ms 14180 KB Output is correct
6 Correct 13 ms 14236 KB Output is correct
7 Correct 11 ms 14248 KB Output is correct
8 Correct 182 ms 20028 KB Output is correct
9 Correct 144 ms 19920 KB Output is correct
10 Correct 149 ms 20424 KB Output is correct
11 Correct 173 ms 20776 KB Output is correct
12 Correct 138 ms 19656 KB Output is correct
13 Correct 143 ms 20232 KB Output is correct
14 Correct 143 ms 20260 KB Output is correct
15 Correct 178 ms 20236 KB Output is correct
16 Correct 129 ms 19996 KB Output is correct
17 Correct 153 ms 20160 KB Output is correct
18 Correct 166 ms 20276 KB Output is correct
19 Correct 154 ms 20352 KB Output is correct
20 Correct 162 ms 20172 KB Output is correct
21 Correct 135 ms 19996 KB Output is correct
22 Correct 192 ms 20084 KB Output is correct
23 Correct 138 ms 19992 KB Output is correct
24 Correct 140 ms 19920 KB Output is correct
25 Correct 172 ms 19912 KB Output is correct
26 Correct 141 ms 19928 KB Output is correct
27 Correct 493 ms 29776 KB Output is correct
28 Correct 437 ms 29588 KB Output is correct
29 Correct 405 ms 29304 KB Output is correct
30 Correct 522 ms 29600 KB Output is correct
31 Correct 440 ms 29648 KB Output is correct
32 Correct 361 ms 28376 KB Output is correct
33 Correct 214 ms 28140 KB Output is correct
34 Correct 215 ms 28092 KB Output is correct
35 Correct 211 ms 28156 KB Output is correct
36 Correct 247 ms 28144 KB Output is correct
37 Correct 189 ms 28088 KB Output is correct
38 Correct 1342 ms 51624 KB Output is correct
39 Correct 1721 ms 56468 KB Output is correct
40 Correct 1072 ms 45440 KB Output is correct
41 Correct 1310 ms 54848 KB Output is correct
42 Correct 421 ms 29428 KB Output is correct
43 Correct 392 ms 29300 KB Output is correct
44 Correct 682 ms 37980 KB Output is correct
45 Correct 629 ms 38100 KB Output is correct
46 Correct 673 ms 38384 KB Output is correct
47 Correct 317 ms 29360 KB Output is correct
48 Correct 259 ms 29160 KB Output is correct
49 Correct 530 ms 38036 KB Output is correct
50 Correct 601 ms 38076 KB Output is correct
51 Correct 572 ms 38452 KB Output is correct
52 Correct 806 ms 36892 KB Output is correct
53 Correct 1188 ms 45800 KB Output is correct
54 Correct 1641 ms 52616 KB Output is correct
55 Correct 1282 ms 46004 KB Output is correct