Submission #582066

#	Time	Username	Problem	Language	Result	Execution time	Memory
582066		urd05	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	1101 ms	219668 KiB

long_mansion

#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];
int l[500001];
int r[500001];
vector<int> lev[500001]; //l[i]의 인버스
vector<int> rev[500001]; //r[i]의 인버스
priority_queue<int,vector<int>,greater<int>> pqr;
priority_queue<int,vector<int>,greater<int>> pre;
priority_queue<int> pql;
priority_queue<int> ple;
vector<P> vl;
vector<P> erl;
vector<P> vr;
vector<P> err;

int main(void) {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        scanf("%d",&c[i]);
        vec[c[i]].push_back(i*2+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());
        v[i].push_back(0);
        v[i].push_back(2*n+2);
        sort(v[i].begin(),v[i].end());
    }
rev[n].push_back(0);
lev[1].push_back(n);
    for(int i=1;i<n;i++) {
        int pos=2*i+1;
        auto iter=lower_bound(v[c[i]].begin(),v[c[i]].end(),pos);
        r[i]=(*iter)/2;
        iter--;
        l[i]=(*iter)/2;
        rev[r[i]].push_back(i);
        lev[l[i]].push_back(i);
    }
    set<int> s;
    for(int i=0;i<rev[n+1].size();i++) {
        s.insert(rev[n+1][i]);
    }
    for(int i=n-1;i>0;i--) {
        for(int j=0;j<rev[i+1].size();j++) {
            s.insert(rev[i+1][j]);
        }
        auto iter=s.lower_bound(l[i]);
        if (iter==s.end()) {
            continue;
        }
        int pos=(*s.lower_bound(l[i]))+1;
        vr.push_back(P(pos,i));
        err.push_back(P(i,i));
    }
    s.clear();
    for(int i=0;i<lev[0].size();i++) {
        s.insert(lev[0][i]);
    }
    for(int i=1;i<n;i++) {
        for(int j=0;j<lev[i].size();j++) {
            s.insert(lev[i][j]);
        }
        auto iter=s.lower_bound(r[i]);
        if (iter==s.begin()) {
            continue;
        }
        iter--;
        int pos=(*iter);
if (i+1<=pos) {
        vl.push_back(P(i+1,i+1));
        erl.push_back(P(pos,i+1));
}
    }
    pql.push(1);
    pqr.push(n);
    int indl=0;
    int indr=0;
    int indle=0;
    int indre=0;
    sort(vl.begin(),vl.end());
    sort(vr.begin(),vr.end());
    sort(erl.begin(),erl.end());
    sort(err.begin(),err.end());
    for(int i=1;i<=n;i++) {
        while(indl<vl.size()&&vl[indl].first==i) {
            pql.push(vl[indl++].second);
        }
        while (indr<vr.size()&&vr[indr].first==i) {
            pqr.push(vr[indr++].second);
        }
        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());
        while(indle<erl.size()&&erl[indle].first==i) {
            ple.push(erl[indle++].second);
        }
        while (indre<err.size()&&err[indre].first==i) {
            pre.push(err[indre++].second);
        }
        //printf("%d %d\n",ret[i].first,ret[i].second);
    }
    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 (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0;i<rev[n+1].size();i++) {
      |                 ~^~~~~~~~~~~~~~~~
long_mansion.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j=0;j<rev[i+1].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~
long_mansion.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<lev[0].size();i++) {
      |                 ~^~~~~~~~~~~~~~
long_mansion.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int j=0;j<lev[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
long_mansion.cpp:103:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         while(indl<vl.size()&&vl[indl].first==i) {
      |               ~~~~^~~~~~~~~~
long_mansion.cpp:106:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while (indr<vr.size()&&vr[indr].first==i) {
      |                ~~~~^~~~~~~~~~
long_mansion.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         while(indle<erl.size()&&erl[indle].first==i) {
      |               ~~~~~^~~~~~~~~~~
long_mansion.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         while (indre<err.size()&&err[indre].first==i) {
      |                ~~~~~^~~~~~~~~~~
long_mansion.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%d",&c[i]);
      |         ~~~~~^~~~~~~~~~~~
long_mansion.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
long_mansion.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~
long_mansion.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 0 / 75