Submission #125483

#	Time	Username	Problem	Language	Result	Execution time	Memory
125483		songc	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1142 ms	72740 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int N, Q;
int C[505050], S[2020202], E[2020202];
int L[505050], R[505050], chk[505050];
int LT[2020202], RT[2020202];
vector<int> key[505050];

void init(int id, int s, int e){
    if (s == e){
        LT[id] = L[s];
        RT[id] = R[s];
        return;
    }
    int mid = (s+e)/2;
    init(id*2, s, mid);
    init(id*2+1, mid+1, e);
    LT[id] = min(LT[id*2], LT[id*2+1]);
    RT[id] = max(RT[id*2], RT[id*2+1]);
}

int Lquery(int id, int s, int e, int ts, int te, int x){
    if (e < ts || te < s || LT[id] > x) return -1;
    if (s == e) return s;
    int mid = (s+e)/2;
    int ret = Lquery(id*2+1, mid+1, e, ts, te, x);
    if (ret != -1) return ret;
    return Lquery(id*2, s, mid, ts, te, x);
}

int Rquery(int id, int s, int e, int ts, int te, int x){
    if (e < ts || te < s || RT[id] <= x) return -1;
    if (s == e) return s+1;
    int mid = (s+e)/2;
    int ret = Rquery(id*2, s, mid, ts, te, x);
    if (ret != -1) return ret;
    return Rquery(id*2+1, mid+1, e, ts, te, x);
}

void updS(int id, int s, int e, int ts, int te, int v){
    if (e < ts || te < s) return;
    if (ts <= s && e <= te){
        S[id] = max(S[id], v);
        return;
    }
    int mid = (s+e)/2;
    updS(id*2, s, mid, ts, te, v);
    updS(id*2+1, mid+1, e, ts, te, v);
}

void updE(int id, int s, int e, int ts, int te, int v){
    if (e < ts || te < s) return;
    if (ts <= s && e <= te){
        E[id] = min(E[id], v);
        return;
    }
    int mid = (s+e)/2;
    updE(id*2, s, mid, ts, te, v);
    updE(id*2+1, mid+1, e, ts, te, v);
}

int readS(int id, int s, int e, int t){
    if (e < t || t < s) return 0;
    if (s == e) return S[id];
    int mid = (s+e)/2;
    return max(S[id], max(readS(id*2, s, mid, t), readS(id*2+1, mid+1, e, t)));
}

int readE(int id, int s, int e, int t){
    if (e < t || t < s) return N+1;
    if (s == e) return E[id];
    int mid = (s+e)/2;
    return min(E[id], min(readE(id*2, s, mid, t), readE(id*2+1, mid+1, e, t)));
}

int main(){
    int x, y;
    scanf("%d", &N);
    for (int i=1; i<N; i++) scanf("%d", &C[i]);
    for (int i=1; i<=N; i++){
        scanf("%d", &x);
        for (int j=0; j<x; j++){
            scanf("%d", &y);
            key[i].push_back(y);
        }
    }
    for (int i=1; i<=N; i++){
        for (int k : key[i]) chk[k] = i;
        L[i] = chk[C[i]];
    }
    memset(chk, 1, sizeof chk);
    for (int i=N; i>=1; i--){
        for (int k : key[i]) chk[k] = i;
        R[i-1] = chk[C[i-1]];
    }
    init(1, 0, N);
    for (int i=1; i<=4*N; i++) S[i] = 1, E[i] = N;
    for (int i=0; i<=N; i++){
        int k = Lquery(1, 0, N, i+1, R[i]-1, i);
        if (k != -1) updS(1, 1, N, i+1, k, i+1);
    }
    for (int i=0; i<=N; i++){
        int k = Rquery(1, 0, N, L[i], i-1, i);
        if (k != -1) updE(1, 1, N, k, i, i);
    }
    scanf("%d", &Q);
    while (Q--){
        scanf("%d %d", &x, &y);
        if (readS(1, 1, N, x) <= y && y <= readE(1, 1, N, x)) puts("YES");
        else puts("NO");
    }
    return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
long_mansion.cpp:81:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<N; i++) scanf("%d", &C[i]);
                             ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
long_mansion.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &y);
             ~~~~~^~~~~~~~~~
long_mansion.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
long_mansion.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75