oj.uz

Submission #129166

# Submission time Handle Problem Language Result Execution time Memory
129166 2019-07-11T18:37:35 Z doowey Long Mansion (JOI17_long_mansion) C++14
5 / 100
 251 ms 28376 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)5e5 + 9;

int value[N * 4 + 512];

void modify(int node,int cl, int cr, int p, int v){
    if(cl == cr){
        value[node] = v;
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= p)
        modify(node * 2, cl, mid, p, v);
    else
        modify(node * 2 + 1, mid + 1, cr, p, v);
    value[node] = min(value[node * 2], value[node * 2 + 1]);
}

int ask(int node, int cl, int cr, int x){
    if(cl == cr)
        return cl;
    int mid = (cl + cr) / 2;
    if(value[node * 2] < x)
        return ask(node * 2, cl, mid, x); 
    else
        return ask(node * 2 + 1, mid + 1, cr, x);
}

int fin(int node, int cl, int cr, int p){
    if(cl == cr){
        return value[node];
    }
    int mid = (cl + cr) / 2;
    if(mid >= p)
        return fin(node * 2, cl, mid, p);
    else
        return fin(node * 2 + 1, mid + 1, cr, p);
}

int gl[N];
int gr[N];
int req[N];
vector<int> col[N];
int las[N];
int lm[N];
int rm[N];

int m;


int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i < n; i ++ )
        cin >> req[i];
    int k, m;
    for(int i = 1; i <= n; i ++ ){
        cin >> k;
        for(int j = 0 ; j < k ; j ++ ){
            cin >> m;
            col[i].push_back(m);
        }
    }
    m = n + 1;
    for(int i = 1; i <= n; i ++ )
        las[i] = n + 1;
    for(int i = n ;i > 1; i -- ){
        for(auto p : col[i])
            las[p] = i;
        gl[i - 1] = las[req[i - 1]];
    }
    for(int i = 1; i <= n ; i ++ )
        las[i] = 0;
    for(int i = 1; i < n; i ++ ){
        for(auto p : col[i])
            las[p] = i;
        gr[i + 1] = las[req[i]];
    }
    modify(1, 1, m, 1, N);
    for(int i = 2; i <= n; i ++ )
        modify(1, 1, m, i, gr[i]);
    vector<int> id;
    rm[1] = ask(1, 1, m, 1) - 1;
    rm[1] = 1;
    lm[1] = 1;
    id.push_back(1);
    for(int i = 2 ; i <= n; i ++ ){
        lm[i] = i;
        rm[i] = i;
        modify(1, 1, m, i, N);
        while(1){
            rm[i] = ask(1, 1, m, lm[i]) - 1;
            if(lm[i] == 1 || gl[lm[i] - 1] > rm[i]) break;
            lm[i] = lm[lm[i] - 1];
        }
    }
    int q;
    cin >> q;
    int x, y;
    for(int i = 0 ; i < q; i ++ ){
        cin >> x >> y;
        if(y >= lm[x] && y <= rm[x])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12280 KB Output is correct
2 Correct 17 ms 12408 KB Output is correct
3 Correct 18 ms 12536 KB Output is correct
4 Correct 16 ms 12280 KB Output is correct
5 Correct 16 ms 12408 KB Output is correct
6 Correct 16 ms 12408 KB Output is correct
7 Correct 16 ms 12280 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12280 KB Output is correct
2 Correct 17 ms 12408 KB Output is correct
3 Correct 18 ms 12536 KB Output is correct
4 Correct 16 ms 12280 KB Output is correct
5 Correct 16 ms 12408 KB Output is correct
6 Correct 16 ms 12408 KB Output is correct
7 Correct 16 ms 12280 KB Output is correct
8 Correct 130 ms 18128 KB Output is correct
9 Correct 130 ms 18104 KB Output is correct
10 Correct 133 ms 18508 KB Output is correct
11 Correct 138 ms 18936 KB Output is correct
12 Correct 119 ms 17916 KB Output is correct
13 Incorrect 127 ms 18408 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 28376 KB Output is correct
2 Correct 251 ms 28208 KB Output is correct
3 Correct 245 ms 27996 KB Output is correct
4 Correct 249 ms 28280 KB Output is correct
5 Correct 249 ms 28152 KB Output is correct
6 Incorrect 215 ms 27000 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12280 KB Output is correct
2 Correct 17 ms 12408 KB Output is correct
3 Correct 18 ms 12536 KB Output is correct
4 Correct 16 ms 12280 KB Output is correct
5 Correct 16 ms 12408 KB Output is correct
6 Correct 16 ms 12408 KB Output is correct
7 Correct 16 ms 12280 KB Output is correct
8 Correct 130 ms 18128 KB Output is correct
9 Correct 130 ms 18104 KB Output is correct
10 Correct 133 ms 18508 KB Output is correct
11 Correct 138 ms 18936 KB Output is correct
12 Correct 119 ms 17916 KB Output is correct
13 Incorrect 127 ms 18408 KB Output isn't correct
14 Halted 0 ms 0 KB -