oj.uz

Submission #581986

# Submission time Handle Problem Language Result Execution time Memory
581986 2022-06-23T09:13:13 Z 조영욱(#8367) Long Mansion (JOI17_long_mansion) C++17
15 / 100
 336 ms 43564 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
int c[100000];
vector<int> vec[100001];
typedef pair<int,int> P;
int cl[100002][21];
int cr[100002][21];
int bl[100002][21];
int br[100002][21];
P ret[100001];

int main(void) {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        scanf("%d",&c[i]);
    }
    for(int i=1;i<=n;i++) {
        int k;
        scanf("%d",&k);
        for(int j=0;j<k;j++) {
            int x;
            scanf("%d",&x);
            vec[i].push_back(x);
        }
    }
    memset(cl,-1,sizeof(cl));
    memset(cr,-1,sizeof(cr));
    memset(bl,-1,sizeof(bl));
    memset(br,-1,sizeof(br));
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=20;j++) {
            bl[i][j]=bl[i-1][j];
        }
        for(int j=0;j<vec[i].size();j++) {
            bl[i][vec[i][j]]=i;
        }
    }
    for(int i=n;i>0;i--) {
        for(int j=1;j<=20;j++) {
            br[i][j]=br[i+1][j];
        }
        for(int j=0;j<vec[i].size();j++) {
            br[i][vec[i][j]]=i;
        }
    }
    for(int i=2;i<=n;i++) {
        for(int j=1;j<=20;j++) {
            cl[i][j]=cl[i-1][j];
        }
        cl[i][c[i-1]]=i-1;
    }
    for(int i=n-1;i>0;i--) {
        for(int j=1;j<=20;j++) {
            cr[i][j]=cr[i+1][j];
        }
        cr[i][c[i]]=i;
    }
    for(int st=1;st<=n;st++) {
        int l=st;
        int r=st;
        bool temp[21];
        memset(temp,0,sizeof(temp));
        while (1) {
            int enl=1;
            int enr=n;
            for(int j=1;j<=20;j++) {
                if ((bl[st][j]!=-1&&bl[st][j]>=l)||(br[st][j]!=-1&&br[st][j]<=r)) {
                    temp[j]=true;
                }
                if (!temp[j]) {
                    if (cl[st][j]!=-1)
                    enl=max(enl,cl[st][j]+1);
                    if (cr[st][j]!=-1)
                    enr=min(enr,cr[st][j]);
                }
            }
            if (l<=enl&&r>=enr) {
                break;
            }
            l=enl;
            r=enr;
        }
        ret[st]=P(l,r);
        //printf("%d %d\n",l,r);
    }
    int q;
    scanf("%d",&q);
    for(int i=0;i<q;i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        if (ret[x].first<=y&&y<=ret[x].second) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
long_mansion.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
long_mansion.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d",&c[i]);
      |         ~~~~~^~~~~~~~~~~~
long_mansion.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
long_mansion.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~
long_mansion.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35668 KB Output is correct
2 Correct 19 ms 35664 KB Output is correct
3 Correct 22 ms 35788 KB Output is correct
4 Incorrect 25 ms 35668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35668 KB Output is correct
2 Correct 19 ms 35664 KB Output is correct
3 Correct 22 ms 35788 KB Output is correct
4 Incorrect 25 ms 35668 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 260 ms 43564 KB Output is correct
2 Correct 250 ms 43408 KB Output is correct
3 Correct 236 ms 43448 KB Output is correct
4 Correct 266 ms 43480 KB Output is correct
5 Correct 272 ms 43524 KB Output is correct
6 Correct 255 ms 42960 KB Output is correct
7 Correct 336 ms 43060 KB Output is correct
8 Correct 312 ms 43004 KB Output is correct
9 Correct 285 ms 43080 KB Output is correct
10 Correct 302 ms 43044 KB Output is correct
11 Correct 303 ms 43004 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35668 KB Output is correct
2 Correct 19 ms 35664 KB Output is correct
3 Correct 22 ms 35788 KB Output is correct
4 Incorrect 25 ms 35668 KB Output isn't correct
5 Halted 0 ms 0 KB -