oj.uz

Submission #582015

# Submission time Handle Problem Language Result Execution time Memory
582015 2022-06-23T09:28:51 Z 조영욱(#8367) Long Mansion (JOI17_long_mansion) C++17
0 / 100
 444 ms 99136 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
int c[500000];
vector<int> vec[500001];
typedef pair<int,int> P;
vector<int> v[500001];
P ret[500001];

vector<int> vl[500001];
vector<int> erl[500001];
vector<int> vr[500001];
vector<int> err[500001];

int main(void) {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        scanf("%d",&c[i]);
        vec[c[i]].push_back(2*i+1);
    }
    for(int i=1;i<=n;i++) {
        int k;
        scanf("%d",&k);
        for(int j=0;j<k;j++) {
            int x;
            scanf("%d",&x);
            v[x].push_back(i*2);
        }
    }
    for(int i=1;i<=n;i++) {
        vec[i].push_back(1);
        vec[i].push_back(2*n+1);
        sort(vec[i].begin(),vec[i].end());
    }
    priority_queue<int,vector<int>,greater<int>> pqr;
    priority_queue<int,vector<int>,greater<int>> pre;
    priority_queue<int> pql;
    priority_queue<int> ple;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<v[i].size();j++) {
            int now=v[i][j];
            int nt=(*lower_bound(vec[i].begin(),vec[i].end(),now));
            vr[now/2].push_back(nt/2);
            err[nt/2].push_back(nt/2);
            auto iter=lower_bound(vec[i].begin(),vec[i].end(),now);
            iter--;
            int pr=(*iter);
            vl[(pr+1)/2].push_back((pr+1)/2);
            erl[now/2].push_back((pr+1)/2);
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=0;j<vl[i].size();j++) {
            pql.push(vl[i][j]);
        }
        for(int j=0;j<vr[i].size();j++) {
            pqr.push(vr[i][j]);
        }
        while (!ple.empty()&&pql.top()==ple.top()) {
            pql.pop();
            ple.pop();
        }
        while (!pre.empty()&&pqr.top()==pre.top()) {
            pre.pop();
            pqr.pop();
        }
        ret[i]=P(pql.top(),pqr.top());
    }
    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:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int j=0;j<v[i].size();j++) {
      |                     ~^~~~~~~~~~~~
long_mansion.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=0;j<vl[i].size();j++) {
      |                     ~^~~~~~~~~~~~~
long_mansion.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0;j<vr[i].size();j++) {
      |                     ~^~~~~~~~~~~~~
long_mansion.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%d",&c[i]);
      |         ~~~~~^~~~~~~~~~~~
long_mansion.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
long_mansion.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~
long_mansion.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 71148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 71148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 444 ms 99136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 71148 KB Output isn't correct
2 Halted 0 ms 0 KB -