oj.uz

Submission #581742

# Submission time Handle Problem Language Result Execution time Memory
581742 2022-06-23T05:32:50 Z 반딧불(#8365) Long Mansion (JOI17_long_mansion) C++17
15 / 100
 564 ms 12780 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    int tree[2000002];

    void init(int i, int l, int r, int *arr){
        if(l==r){
            tree[i] = arr[l];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, arr);
        init(i*2+1, m+1, r, arr);
        tree[i] = tree[i*2] | tree[i*2+1];
    }

    int queryL(int i, int l, int r, int x, int st){ /// x ���� �� st �κ������� �ƴ� ���� ������ ���� ������
        if((tree[i]&st) == tree[i]) return l-1;
        if(x<l) return l-1;
        if(l==r) return l;
        int m = (l+r)>>1;
        int tmp = queryL(i*2+1, m+1, r, x, st);
        if(tmp==m) return queryL(i*2, l, m, x, st);
        return tmp;
    }

    int queryR(int i, int l, int r, int x, int st){
        if((tree[i]&st) == tree[i]) return r+1;
        if(r<x) return r+1;
        if(l==r) return r;
        int m = (l+r)>>1;
        int tmp = queryR(i*2, l, m, x, st);
        if(tmp==m+1) return queryR(i*2+1, m+1, r, x, st);
        return tmp;
    }

    int query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e) | query(i*2+1, m+1, r, s, e);
    }
} tree, tree2;

int n, q;
int arr[500002]; /// arr[i]: i�� i+1 ����
int state[500002];
int l[500002], r[500002];

int main(){
    scanf("%d", &n);
    for(int i=1; i<n; i++){
        scanf("%d", &arr[i]);
        arr[i] = 1<<arr[i];
    }
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        for(int j=0; j<x; j++){
            int y;
            scanf("%d", &y);
            state[i] |= (1<<y);
        }
    }

    tree.init(1, 1, n-1, arr);
    tree2.init(1, 1, n, state);
    for(int i=1; i<=n; i++){
        l[i] = r[i] = i;
        int st = state[i];
        while(1){
            int l2 = tree.queryL(1, 1, n-1, i-1, st)+1;
            int r2 = tree.queryR(1, 1, n-1, i, st);
            if(l[i]==l2 && r[i]==r2) break;
            l[i] = l2, r[i] = r2;
            st = tree2.query(1, 1, n, l[i], r[i]);
        }
    }

    scanf("%d", &q);
    while(q--){
        int s, e;
        scanf("%d %d", &s, &e);
        printf("%s\n", (l[s] <= e && e <= r[s]) ? "YES" : "NO");
    }
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
long_mansion.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
long_mansion.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |             scanf("%d", &y);
      |             ~~~~~^~~~~~~~~~
long_mansion.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
long_mansion.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%d %d", &s, &e);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 588 KB Output is correct
4 Incorrect 10 ms 480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 588 KB Output is correct
4 Incorrect 10 ms 480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 12040 KB Output is correct
2 Correct 267 ms 12700 KB Output is correct
3 Correct 285 ms 12640 KB Output is correct
4 Correct 251 ms 12780 KB Output is correct
5 Correct 293 ms 12728 KB Output is correct
6 Correct 380 ms 12156 KB Output is correct
7 Correct 492 ms 12176 KB Output is correct
8 Correct 513 ms 11952 KB Output is correct
9 Correct 564 ms 11984 KB Output is correct
10 Correct 454 ms 11872 KB Output is correct
11 Correct 495 ms 12068 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 588 KB Output is correct
4 Incorrect 10 ms 480 KB Output isn't correct
5 Halted 0 ms 0 KB -