oj.uz

Submission #581851

# Submission time Handle Problem Language Result Execution time Memory
581851 2022-06-23T07:22:06 Z 박상훈(#8364) Long Mansion (JOI17_long_mansion) C++17
15 / 100
 405 ms 48380 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Seg{
    int tree[1001000], sz;
    void init(int n, int *a){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
        for (int i=sz-1;i;i--) tree[i] = tree[i<<1] | tree[i<<1|1];
    }
    int query(int l, int r){
        int ret = 0;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret |= tree[l++];
            if (r&1) ret |= tree[--r];
        }
        return ret;
    }
}tree;
vector<int> keys[500500], pos[500500];
int c[500500], L[500500], R[500500], kbt[500500], cur;
int n;

void calc(int s){
    cur = kbt[s];
    L[s] = s, R[s] = s;

    vector<pair<int, int>> VL = {{0, 21}}, VR = {{n, 21}};
    for (int i=1;i<=20;i++){
        int idx = lower_bound(pos[i].begin(), pos[i].end(), s) - pos[i].begin();
        if (idx>0) VL.emplace_back(pos[i][idx-1], i);
        if (idx<(int)pos[i].size()) VR.emplace_back(pos[i][idx], i);
    }
    sort(VL.begin(), VL.end());
    sort(VR.begin(), VR.end(), greater<pair<int, int>>());

    while(true){
        while(cur & (1<<VL.back().second)) VL.pop_back();
        while(cur & (1<<VR.back().second)) VR.pop_back();

        int nL = VL.back().first + 1;
        int nR = VR.back().first;

        if (nL==L[s] && nR==R[s]) break;

        L[s] = nL;
        R[s] = nR;

        cur = tree.query(L[s], R[s]+1);

    }
}

int main(){
    scanf("%d", &n);
    for (int i=1;i<=n-1;i++){
        scanf("%d", c+i);
        pos[c[i]].push_back(i);
    }

    for (int i=1;i<=n;i++){
        int x;
        scanf("%d", &x);
        for (int j=1;j<=x;j++){
            int y;
            scanf("%d", &y);
            keys[i].push_back(y);
            kbt[i] |= (1<<y);
        }
    }

    tree.init(n+1, kbt);

    for (int i=1;i<=n;i++) calc(i);

    int q;
    scanf("%d", &q);
    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        if (L[x] <= y && y <= R[x]) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
long_mansion.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d", c+i);
      |         ~~~~~^~~~~~~~~~~
long_mansion.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |             scanf("%d", &y);
      |             ~~~~~^~~~~~~~~~
long_mansion.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
long_mansion.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 17 ms 24004 KB Output is correct
3 Correct 17 ms 24168 KB Output is correct
4 Runtime error 33 ms 48380 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 17 ms 24004 KB Output is correct
3 Correct 17 ms 24168 KB Output is correct
4 Runtime error 33 ms 48380 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 37656 KB Output is correct
2 Correct 331 ms 38256 KB Output is correct
3 Correct 297 ms 38232 KB Output is correct
4 Correct 382 ms 38288 KB Output is correct
5 Correct 360 ms 38392 KB Output is correct
6 Correct 384 ms 37876 KB Output is correct
7 Correct 405 ms 37900 KB Output is correct
8 Correct 390 ms 38036 KB Output is correct
9 Correct 401 ms 37804 KB Output is correct
10 Correct 400 ms 38012 KB Output is correct
11 Correct 400 ms 37736 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 17 ms 24004 KB Output is correct
3 Correct 17 ms 24168 KB Output is correct
4 Runtime error 33 ms 48380 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -