oj.uz

Submission #206998

# Submission time Handle Problem Language Result Execution time Memory
206998 2020-03-06T04:03:16 Z nvmdava Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 18296 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 524288
#define MOD 1000000007
#define INF 0x3f3f3f3f

int c[N];
int n;

vector<int> loc[N];

int le[N], ri[N];

bool query(int l, int r, int c){
    auto it = lower_bound(loc[c].begin(), loc[c].end(), l);
    return it != loc[c].end() && *it <= r;
}

void dnc(int l, int r){
    if(l > r) return;
    int m = (l + r) >> 1;
    int L = m, R = m;
    bool ok;
    do {
        ok = 0;
        while(query(L, R, c[R])){
            ++R;
            ok = 1;
            if(ri[R]){
                L = min(L, le[R]);
                R = max(R, ri[R]);
            }
        }
        while(query(L, R, c[L - 1])){
            --L;
            ok = 1;
            if(le[L]){
                R = max(R, ri[L]);
                L = min(L, le[L]);
            }
        }
    } while (ok == 1);
    le[m] = L;
    ri[m] = R;
    dnc(max(L, l), m - 1);
    dnc(m + 1, min(r, R));
    dnc(l, L - 1);
    dnc(R + 1, r);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i = 1; i < n; ++i){
        cin>>c[i];
    }
    for(int b, k, i = 1; i <= n; ++i){
        cin>>b;
        while(b--){
            cin>>k;
            loc[k].push_back(i);
        }
    }
    dnc(1, n);
    int q;
    cin>>q;
    while(q--){
        int x, y;
        cin>>x>>y;
        if(le[x] <= y && y <= ri[x])
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12792 KB Output is correct
2 Correct 17 ms 12792 KB Output is correct
3 Correct 20 ms 12920 KB Output is correct
4 Correct 15 ms 12792 KB Output is correct
5 Correct 15 ms 12792 KB Output is correct
6 Correct 15 ms 12792 KB Output is correct
7 Correct 14 ms 12920 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12792 KB Output is correct
2 Correct 17 ms 12792 KB Output is correct
3 Correct 20 ms 12920 KB Output is correct
4 Correct 15 ms 12792 KB Output is correct
5 Correct 15 ms 12792 KB Output is correct
6 Correct 15 ms 12792 KB Output is correct
7 Correct 14 ms 12920 KB Output is correct
8 Correct 128 ms 14748 KB Output is correct
9 Correct 120 ms 14460 KB Output is correct
10 Correct 127 ms 14712 KB Output is correct
11 Correct 128 ms 14840 KB Output is correct
12 Correct 115 ms 14712 KB Output is correct
13 Correct 128 ms 14712 KB Output is correct
14 Correct 124 ms 14736 KB Output is correct
15 Correct 119 ms 14840 KB Output is correct
16 Correct 118 ms 14968 KB Output is correct
17 Correct 121 ms 14712 KB Output is correct
18 Correct 128 ms 14712 KB Output is correct
19 Correct 123 ms 14840 KB Output is correct
20 Correct 116 ms 15096 KB Output is correct
21 Correct 117 ms 15096 KB Output is correct
22 Correct 122 ms 14844 KB Output is correct
23 Correct 119 ms 14712 KB Output is correct
24 Correct 121 ms 14712 KB Output is correct
25 Correct 122 ms 14712 KB Output is correct
26 Correct 127 ms 14840 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3090 ms 18296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12792 KB Output is correct
2 Correct 17 ms 12792 KB Output is correct
3 Correct 20 ms 12920 KB Output is correct
4 Correct 15 ms 12792 KB Output is correct
5 Correct 15 ms 12792 KB Output is correct
6 Correct 15 ms 12792 KB Output is correct
7 Correct 14 ms 12920 KB Output is correct
8 Correct 128 ms 14748 KB Output is correct
9 Correct 120 ms 14460 KB Output is correct
10 Correct 127 ms 14712 KB Output is correct
11 Correct 128 ms 14840 KB Output is correct
12 Correct 115 ms 14712 KB Output is correct
13 Correct 128 ms 14712 KB Output is correct
14 Correct 124 ms 14736 KB Output is correct
15 Correct 119 ms 14840 KB Output is correct
16 Correct 118 ms 14968 KB Output is correct
17 Correct 121 ms 14712 KB Output is correct
18 Correct 128 ms 14712 KB Output is correct
19 Correct 123 ms 14840 KB Output is correct
20 Correct 116 ms 15096 KB Output is correct
21 Correct 117 ms 15096 KB Output is correct
22 Correct 122 ms 14844 KB Output is correct
23 Correct 119 ms 14712 KB Output is correct
24 Correct 121 ms 14712 KB Output is correct
25 Correct 122 ms 14712 KB Output is correct
26 Correct 127 ms 14840 KB Output is correct
27 Execution timed out 3090 ms 18296 KB Time limit exceeded
28 Halted 0 ms 0 KB -