제출 #635897

#제출 시각아이디문제언어결과실행 시간메모리
635897Cross_RatioLong Mansion (JOI17_long_mansion)C++14
10 / 100
3038 ms20284 KiB
#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]--;
    }
    for(i=0;i<N;i++) {
        L[i] = i;
        R[i] = i;
        set<int> S;
        for(int n : A[i]) S.insert(n);
        if(i&&S.find(C[i-1])!=S.end()) {
            if(R[i-1] >= i) {
                R[i] = R[i-1];
                L[i] = L[i-1];
                continue;
            }
            L[i] = min(L[i-1], L[i]);
        }
        int pt = i;
        while(pt!=L[i]) {
            pt--;
            for(int n : A[pt]) S.insert(n);
        }
        int pL = L[i], pR = R[i];
        while(true) {
            while(L[i]&& S.find(C[L[i]-1])!=S.end()) {
                L[i]--;
                for(int n : A[L[i]]) S.insert(n);
            }
            while(R[i]+1<N&&S.find(C[R[i]])!=S.end()) {
                R[i]++;
                for(int n : A[R[i]]) S.insert(n);
            }
            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]--;
      |                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...