제출 #635901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635901		Cross_Ratio	Long Mansion (JOI17_long_mansion)	C++14	15 / 100	434 ms	25284 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;
    bool type; // 0 : ma, 1 : mi
    SegTree(int N, bool c) {
        type = c;
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
        for(i=0;i<MAX;i++) {
            seg[i] = (c?INF:-INF);
        }
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = (type ? min(seg[2*i], seg[2*i+1]) : max(seg[2*i], seg[2*i+1]));
        }
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg[n] = (type ? min(seg[2*n], seg[2*n+1]) : max(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 (type ? INF : -INF);
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        int v1 = sum(s, e, 2*n, ns, mid);
        int v2 = sum(s, e, 2*n+1, mid, ne);
        return (type ? min(v1,v2) : max(v1,v2));
    }
};
struct SegTree2 {
    vector<int> seg;
    int MAX;
    SegTree2(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = seg[2*i] | seg[2*i+1];
        }
    }
    void update(int n) {
        n += MAX/2;
        n /= 2;
        while(n) {
            seg[n] = 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 0;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        int v1 = sum(s, e, 2*n, ns, mid);
        int v2 = sum(s, e, 2*n+1, mid, ne);
        return v1|v2;
    }
};
int L[500005];
int R[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]--;
    }
    SegTree2 tree3(N), tree4(N);
    int MAX = tree3.MAX;
    for(i=0;i<N;i++) {
        int s = 0;
        for(int n : A[i]) s += (1<<n);
        tree3.seg[i+MAX/2] = s;
    }
    for(i=1;i<N;i++) {
        tree4.seg[i+MAX/2] = (1<<C[i-1]);
    }
    tree3.cons();
    tree4.cons();
    for(i=0;i<N;i++) {
        L[i] = i;
        R[i] = i;
        int S = 0;
        for(int n : A[i]) S += (1<<n);
        if(i&& ( (1<<(C[i-1]))&S) == (1<<(C[i-1])) ) {
            if(R[i-1] >= i) {
                R[i] = R[i-1];
                L[i] = L[i-1];
                continue;
            }
            L[i] = min(L[i-1], L[i]);
        }
        S |= tree3.sum(L[i], i+1, 1, 0, MAX/2);
        int pL = L[i], pR = R[i];
        while(true) {
            while(L[i] && ( (1<<(C[L[i]-1]))&S) == (1<<(C[L[i]-1])) ) {
                L[i] = min(L[i]-1, L[L[i]-1]);
                S |= tree3.sum(L[i], R[i]+1, 1, 0, MAX/2);
            }
            int s = R[i], e = N;
            while(s+1<e) {
                int mid = (s+e)/2;
                int L = tree4.sum(R[i]+1, mid+1, 1, 0, MAX/2);
                if((L&S)==L) {
                    s = mid;
                }
                else e = mid;
            }
            S |= tree3.sum(R[i], s+1, 1, 0, MAX/2);
            R[i] = s;
            if(pL==L[i]&&pR==R[i]) break;
            pL= L[i];
            pR = R[i];
        }
    }
}
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");
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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