oj.uz

Submission #206997

# Submission time Handle Problem Language Result Execution time Memory
206997 2020-03-06T04:00:12 Z nvmdava Long Mansion (JOI17_long_mansion) C++17
0 / 100
 2684 ms 262148 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(L, m - 1);
    dnc(m + 1, 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 337 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 337 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2684 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 337 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -