Submission #636736

#	Time	Username	Problem	Language	Result	Execution time	Memory
636736		Cross_Ratio	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	334 ms	107204 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int N;
int C[500005];
vector<vector<int>> A;
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
        for(i=0;i<MAX;i++) {
            seg[i] = INF;
        }
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = min(seg[2*i], seg[2*i+1]);
        }
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg[n] = min(seg[2*n], seg[2*n+1]);
            n /= 2;
        }
    }
    void Edit(int n, int a) {
        seg[n+MAX/2] = a;
        update(n);
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return INF;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return min(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
    }
    int get_right(int s, int e, int k, int n, int ns, int ne) {
        if(e<=ns||ne<=s||seg[n]>=k) return -1;
        if(n>=MAX/2) return ns;
        int mid = (ns + ne) / 2;
        int c = get_right(s, e, k, 2*n, ns, mid);
        if(c != -1) return c;
        return get_right(s, e, k, 2*n+1, mid, ne);
    }
};
int L[500005];
int R[500005];
int prv[500005];
int nxt[500005];
int D[500005];
void init(vector<int> _C, vector<vector<int>> _A) {
    N = _A.size();
    A = _A;
    int i, j;
    for(i=0;i<N-1;i++) C[i] = _C[i] - 1;
    for(i=0;i<N;i++) {
        for(j=0;j<A[i].size();j++) A[i][j]--;
    }
    for(i=0;i<N;i++) D[i] = -1;
    for(i=0;i<N;i++) {
        prv[i] = (i == 0 ? -1 : D[C[i-1]]);
        for(int n : A[i]) D[n] = i;
    }
    for(i=0;i<N;i++) D[i] = N;
    for(i=N-1;i>=0;i--) {
        nxt[i] = (i == N-1 ? N : D[C[i]]);
        for(int n : A[i]) D[n] = i;
    }
    SegTree tree(N+5);
    int MAX = tree.MAX;
    for(i=0;i<N;i++) {
        tree.seg[i+MAX/2] = prv[i];
        //tree.Edit(i, prv[i]);
    }
    tree.cons();
    for(i=0;i<N;i++) {
        L[i] = i;
        R[i] = i;
        int pL = L[i], pR = R[i];
        while(true) {
            if(R[i] < N-1) R[i] = tree.get_right(R[i]+1, N, L[i], 1, 0, MAX/2) - 1;
            if(R[i]==-2) R[i] = N-1;
            if(L[i] >= 1 && nxt[L[i]-1] <= R[i]) {
                L[i] = L[L[i]-1];
            }
            if(pL==L[i]&&pR==R[i]) break;
            pL= L[i];
            pR = R[i];
        }
        //cout << i << " : " << L[i] <<' ' << R[i] << '\n';
    }
}
bool isPos(int a, int b) {
    a--;
    b--;
    return L[a]<=b&&b<=R[a];
}






signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    vector<int> c(N-1);
    for(i=0;i<N-1;i++) cin >> c[i];
    vector<vector<int>> a(N);
    for(i=0;i<N;i++) {
        int sz;
        cin >> sz;
        a[i].resize(sz);
        for(j=0;j<sz;j++) cin >> a[i][j];
    }
    init(c, a);
    int Q;
    cin >> Q;
    while(Q--) {
        int x, y;
        cin >> x >> y;
        cout << (isPos(x, y) ? "YES\n": "NO\n");
    }
}

Compilation message (stderr)

long_mansion.cpp: In member function 'int SegTree::sum(int, int, int, int, int)':
long_mansion.cpp:39:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
long_mansion.cpp: In function 'void init(std::vector<int>, std::vector<std::vector<int> >)':
long_mansion.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(j=0;j<A[i].size();j++) A[i][j]--;
      |                 ~^~~~~~~~~~~~

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