oj.uz

Submission #958580

# Submission time Handle Problem Language Result Execution time Memory
958580 2024-04-06T04:59:09 Z Alish Long Mansion (JOI17_long_mansion) C++17
100 / 100
 294 ms 59888 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("tests.in" , "r" , stdin) ;

ll mod = 1e9+7 ;

const int N = 5e5+23;

int seg[4*N];
int L[N], R[N];
vector<int> a[N];
int b[N], c[N];
int ind[N], pre[N], nxt[N];
int n, q;

void build(int l=0, int r=n+2, int ind=0){
    if(r-l==1){
        seg[ind]=pre[l];
        return;
    }
    int mid=(r+l)>>1;
    build(l, mid, 2*ind+1); build(mid, r, 2*ind+2);
    seg[ind]=min(seg[2*ind+1], seg[2*ind+2]);
}

int get(int lx, int rx, int x, int l=0, int r=n+2, int ind=0){
    if(lx>=r || rx<=l || seg[ind]>=x) return -1;
    if(r-l==1) return l;
    int mid=(r+l)>>1;
    int r1=get(lx, rx, x, l, mid, 2*ind+1);
    if(r1==-1) return get(lx, rx, x, mid, r, 2*ind+2);
    return r1;
}

int main()
{
    fast_io
    cin>>n;
    for (int i=1; i<n; i++) cin>>c[i];
    for (int i=1; i<=n; i++){
        cin>>b[i];
        for (int j=0; j<b[i]; j++){
            int x; cin>>x;
            a[i].pb(x);
        }
    }
    for (int i=1; i<=n; i++){
        pre[i]=ind[c[i-1]];
        for (int j: a[i]) ind[j]=i;
    }
    for (int i=0; i<=n; i++) ind[i]=n+1;
    for (int i=n; i>=1; i--){
        nxt[i]=ind[c[i]];
        for (int j: a[i]) ind[j]=i;
    }
    nxt[0]=n+1;
    pre[n+1]=0;
    build();
    for (int i=1; i<=n; i++){
        L[i]=R[i]=i;
        while(1){
            int preL=L[i], preR=R[i];
            R[i]=get(R[i]+1, n+2, L[i])-1;
            if(nxt[L[i]-1]<=R[i]) L[i]=L[L[i]-1];
            if(L[i]==preL && R[i]==preR) break;
        }
    }
    cin>>q;
    while(q--){
        int x, y; cin>>x>>y;
        if(L[x]<=y && y<=R[x]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25180 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 9 ms 25376 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 8 ms 25268 KB Output is correct
7 Correct 7 ms 25180 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25180 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 9 ms 25376 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 8 ms 25268 KB Output is correct
7 Correct 7 ms 25180 KB Output is correct
8 Correct 77 ms 31056 KB Output is correct
9 Correct 80 ms 30860 KB Output is correct
10 Correct 80 ms 31316 KB Output is correct
11 Correct 84 ms 31840 KB Output is correct
12 Correct 90 ms 30548 KB Output is correct
13 Correct 76 ms 31108 KB Output is correct
14 Correct 89 ms 31312 KB Output is correct
15 Correct 78 ms 31008 KB Output is correct
16 Correct 80 ms 31000 KB Output is correct
17 Correct 76 ms 31256 KB Output is correct
18 Correct 105 ms 31512 KB Output is correct
19 Correct 77 ms 31132 KB Output is correct
20 Correct 76 ms 31060 KB Output is correct
21 Correct 75 ms 31036 KB Output is correct
22 Correct 78 ms 30968 KB Output is correct
23 Correct 76 ms 30804 KB Output is correct
24 Correct 78 ms 30980 KB Output is correct
25 Correct 79 ms 30956 KB Output is correct
26 Correct 78 ms 30900 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 38480 KB Output is correct
2 Correct 150 ms 38168 KB Output is correct
3 Correct 141 ms 37976 KB Output is correct
4 Correct 147 ms 38416 KB Output is correct
5 Correct 164 ms 38404 KB Output is correct
6 Correct 138 ms 36948 KB Output is correct
7 Correct 130 ms 36692 KB Output is correct
8 Correct 133 ms 36660 KB Output is correct
9 Correct 128 ms 36688 KB Output is correct
10 Correct 126 ms 36688 KB Output is correct
11 Correct 156 ms 36656 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25180 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 9 ms 25376 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 8 ms 25268 KB Output is correct
7 Correct 7 ms 25180 KB Output is correct
8 Correct 77 ms 31056 KB Output is correct
9 Correct 80 ms 30860 KB Output is correct
10 Correct 80 ms 31316 KB Output is correct
11 Correct 84 ms 31840 KB Output is correct
12 Correct 90 ms 30548 KB Output is correct
13 Correct 76 ms 31108 KB Output is correct
14 Correct 89 ms 31312 KB Output is correct
15 Correct 78 ms 31008 KB Output is correct
16 Correct 80 ms 31000 KB Output is correct
17 Correct 76 ms 31256 KB Output is correct
18 Correct 105 ms 31512 KB Output is correct
19 Correct 77 ms 31132 KB Output is correct
20 Correct 76 ms 31060 KB Output is correct
21 Correct 75 ms 31036 KB Output is correct
22 Correct 78 ms 30968 KB Output is correct
23 Correct 76 ms 30804 KB Output is correct
24 Correct 78 ms 30980 KB Output is correct
25 Correct 79 ms 30956 KB Output is correct
26 Correct 78 ms 30900 KB Output is correct
27 Correct 147 ms 38480 KB Output is correct
28 Correct 150 ms 38168 KB Output is correct
29 Correct 141 ms 37976 KB Output is correct
30 Correct 147 ms 38416 KB Output is correct
31 Correct 164 ms 38404 KB Output is correct
32 Correct 138 ms 36948 KB Output is correct
33 Correct 130 ms 36692 KB Output is correct
34 Correct 133 ms 36660 KB Output is correct
35 Correct 128 ms 36688 KB Output is correct
36 Correct 126 ms 36688 KB Output is correct
37 Correct 156 ms 36656 KB Output is correct
38 Correct 217 ms 56540 KB Output is correct
39 Correct 236 ms 59888 KB Output is correct
40 Correct 200 ms 51956 KB Output is correct
41 Correct 294 ms 58196 KB Output is correct
42 Correct 130 ms 38004 KB Output is correct
43 Correct 131 ms 37976 KB Output is correct
44 Correct 186 ms 46024 KB Output is correct
45 Correct 187 ms 46232 KB Output is correct
46 Correct 197 ms 46672 KB Output is correct
47 Correct 134 ms 38096 KB Output is correct
48 Correct 151 ms 37824 KB Output is correct
49 Correct 196 ms 46236 KB Output is correct
50 Correct 204 ms 46216 KB Output is correct
51 Correct 207 ms 46676 KB Output is correct
52 Correct 166 ms 45040 KB Output is correct
53 Correct 207 ms 52308 KB Output is correct
54 Correct 254 ms 57472 KB Output is correct
55 Correct 203 ms 52436 KB Output is correct