제출 #993430

#제출 시각아이디문제언어결과실행 시간메모리
993430modwweLong Mansion (JOI17_long_mansion)C++17
100 / 100
846 ms103800 KiB
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2") #include<bits/stdc++.h> //#define int long long //#define ll long long #define down cout<<'\n'; #define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".out","w",stdout) #define pb push_back #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; void phongbeo(); const int mod2=998244353; const int mod1=998244353; struct icd { int a,b; }; struct ib { int a; int b; }; struct ic { int a,b,c; }; struct id { int a,b,c,d; }; struct ie { int a,b,c, d,e,f; }; int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l; int i,s10,s12; int el=29; main() { #ifndef ONLINE_JUDGE // fin(task),fou(task); #endif NHP /// cin>>s1; ///modwwe phongbeo(); } struct IT { int t[2000001]; void upd(int node,int l,int r,int l1,int r1,int c ) { if(l1>r1) return; if(l>r1||r<l1)return; if(l>=l1&&r<=r1) { t[node]=c; return; } if(t[node]!=0) { t[node<<1]=t[node]; t[node<<1|1]=t[node]; t[node]=0; } int mid=l+r>>1; upd(node<<1,l,mid,l1,r1,c); upd(node<<1|1,mid+1,r,l1,r1,c); } int get(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return 0; if(l>=l1&&r<=r1) return t[node]; if(t[node]!=0) { t[node<<1]=t[node]; t[node<<1|1]=t[node]; t[node]=0; } int mid=l+r>>1; return get(node<<1,l,mid,l1,r1)+get(node<<1|1,mid+1,r,l1,r1); } } st1,st2; struct IT2 { int t[2000001]; void reset(int node,int l,int r) { t[node]=n+1; if(l==r) return; int mid=l+r>>1; reset(node<<1,l,mid); reset(node<<1|1,mid+1,r); } void upd(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return ; if(l>=l1&&r<=r1) { t[node]=l; return; } int mid=l+r>>1; upd(node<<1,l,mid,l1,r1); upd(node<<1|1,mid+1,r,l1,r1); t[node]=max(t[node<<1],t[node<<1|1]); } void upd2(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return ; if(l>=l1&&r<=r1) { t[node]=l; return; } int mid=l+r>>1; upd2(node<<1,l,mid,l1,r1); upd2(node<<1|1,mid+1,r,l1,r1); t[node]=min(t[node<<1],t[node<<1|1]); } int get2(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return n+1; if(l>=l1&&r<=r1)return t[node]; int mid=l+r>>1; return min(get2(node<<1,l,mid,l1,r1),get2(node<<1|1,mid+1,r,l1,r1)); } int get(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return 0; if(l>=l1&&r<=r1)return t[node]; int mid=l+r>>1; return max(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1)); } } ss; int a[500001]; ib b[500001]; vector<int> v[500003]; vector<int> v2[500003]; vector<int> v3[500003]; void setup() { st1.upd(1,1,n,1,n,1); st2.upd(1,1,n,1,n,n); for(int i=1; i<n; i++) { s2=upper_bound(v[a[i]].begin(),v[a[i]].end(),i)-v[a[i]].begin(); s2--; s3=v[a[i]][s2]+1; b[i].a=s3; v2[s3-1].pb(i+1); s2=lower_bound(v[a[i]].begin(),v[a[i]].end(),i+1)-v[a[i]].begin(); s3=v[a[i]][s2]-1; b[i].b=s3; v3[s3+1].pb(i); } } void solve1() { for(int i=0; i<n; i++) { /// di tu trai sang s3=b[i].b+1; ///i+1->s3 for(auto x:v2[i]) ss.upd(1,1,n,x,x); if(i==0) continue; if(s3==n+1) { st1.upd(1,1,n,i+1,n,i+1); continue; } s4=ss.get(1,1,n,i+2,s3); st1.upd(1,1,n,i+1,s4-1,i+1); } } void solve2() { ss.reset(1,1,n); for(int i=n; i>=1; --i) { s3=b[i].a-1; for(auto x:v3[i+1]) ss.upd2(1,1,n,x,x); if(i>=n) continue; if(s3==0) { st2.upd(1,1,n,1,i,i); continue; } s4=ss.get2(1,1,n,s3,i); st2.upd(1,1,n,s4+1,i,i); //cout<<s4+1<<" "<<i<<" "<<s3,down } } void phongbeo() { cin>>n; for(int i=1; i<n; i++) cin>>a[i],v[i].pb(0); v[n].pb(0); for(int i=1; i<=n; i++) { cin>>k; for(int j=1; j<=k; j++) { cin>>l; v[l].pb(i); } } for(int i=1; i<=n; i++) v[i].pb(n+1); setup(); solve1(); solve2(); cin>>m; for(int i=1; i<=m; i++) { cin>>l>>r; if(r>l) { s4=st2.get(1,1,n,l,l); if(s4>=r) { cout<<"YES"; } else cout<<"NO"; } else { s4=st1.get(1,1,n,l,l); if(s4<=r) { cout<<"YES"; } else cout<<"NO"; } cout<<"\n"; } }

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

long_mansion.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~
long_mansion.cpp: In member function 'void IT::upd(int, int, int, int, int, int)':
long_mansion.cpp:73:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'int IT::get(int, int, int, int, int)':
long_mansion.cpp:87:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'void IT2::reset(int, int, int)':
long_mansion.cpp:98:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'void IT2::upd(int, int, int, int, int)':
long_mansion.cpp:110:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'void IT2::upd2(int, int, int, int, int)':
long_mansion.cpp:123:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'int IT2::get2(int, int, int, int, int)':
long_mansion.cpp:132:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |         int mid=l+r>>1;
      |                 ~^~
long_mansion.cpp: In member function 'int IT2::get(int, int, int, int, int)':
long_mansion.cpp:139:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |         int mid=l+r>>1;
      |                 ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...