제출 #432187

#제출 시각아이디문제언어결과실행 시간메모리
432187jamezzzLong Mansion (JOI17_long_mansion)C++17
100 / 100
506 ms41412 KiB
#include <bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define fi first #define se second #define pb emplace_back #define sz(x) (int)x.size() #define INF 1023456789 #define LINF 1023456789123456789 #define all(x) x.begin(), x.end() typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<pll> vll; mt19937 rng(time(0)); #define maxn 500005 int n,c[maxn],b,t,q,x,y,cl[maxn],cr[maxn],l[maxn],r[maxn]; vi v[maxn]; bool can(int x,int l,int r){ //current range is [l,r], can u travel through door x int pos=lower_bound(all(v[c[x]]),l)-v[c[x]].begin(); if(pos==sz(v[c[x]])||v[c[x]][pos]>r)return false; return true; } ii thing(int l,int r){ if(l>1&&can(l-1,l,r))return thing(cl[l-1],r); if(r<n&&can(r,l,r))return thing(l,cr[r+1]); return ii(l,r); } int main(){ sf("%d",&n); for(int i=1;i<n;++i)sf("%d",&c[i]); for(int i=1;i<=n;++i){ sf("%d",&b); for(int j=0;j<b;++j){ sf("%d",&t); v[t].pb(i); } } for(int i=1;i<=n;++i){ cl[i]=i; while(1<cl[i]&&can(cl[i]-1,cl[i],i))cl[i]=cl[cl[i]-1]; } for(int i=n;i>=1;--i){ cr[i]=i; while(cr[i]<n&&can(cr[i],i,cr[i]))cr[i]=cr[cr[i]+1]; } for(int i=1;i<=n;++i){ if(i>1&&can(i-1,i,cr[i])){ l[i]=l[i-1]; r[i]=max(r[i-1],cr[i]); } else{ l[i]=cl[i];r[i]=cr[i]; } tie(l[i],r[i])=thing(l[i],r[i]); } sf("%d",&q); while(q--){ sf("%d%d",&x,&y); if(l[x]<=y&&y<=r[x])pf("YES\n"); else pf("NO\n"); } }

컴파일 시 표준 에러 (stderr) 메시지

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:43:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  sf("%d",&n);
      |    ^
long_mansion.cpp:44:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  for(int i=1;i<n;++i)sf("%d",&c[i]);
      |                        ^
long_mansion.cpp:46:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   sf("%d",&b);
      |     ^
long_mansion.cpp:48:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |    sf("%d",&t);
      |      ^
long_mansion.cpp:70:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  sf("%d",&q);
      |    ^
long_mansion.cpp:72:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   sf("%d%d",&x,&y);
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...