제출 #582057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582057		urd05	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	1302 ms	262144 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<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(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[pos].push_back(i);
        err[i].push_back(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[i+1].push_back(i+1);
        erl[pos].push_back(i+1);
}
    }
    pql.push(1);
    pqr.push(n);
    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());
        for(int j=0;j<erl[i].size();j++) {
            ple.push(erl[i][j]);
        }
        for(int j=0;j<err[i].size();j++) {
            pre.push(err[i][j]);
        }
        //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");
        }
    }
}

컴파일 시 표준 에러 (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:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int j=0;j<vl[i].size();j++) {
      |                     ~^~~~~~~~~~~~~
long_mansion.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(int j=0;j<vr[i].size();j++) {
      |                     ~^~~~~~~~~~~~~
long_mansion.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int j=0;j<erl[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
long_mansion.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for(int j=0;j<err[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
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:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
long_mansion.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

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