Submission #1205775

#TimeUsernameProblemLanguageResultExecution timeMemory
1205775AiperiiiStranded Far From Home (BOI22_island)C++20
15 / 100
107 ms30652 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(),x.end() #define ff first #define ss second #define pb push_back const int N=2e5+5; vector <int> g[N]; int sum[N],a[N],ok[N]; pair <int,int> t[N*4]; int n,m; void build(int v,int tl,int tr){ if(tl==tr){ t[v]={a[tl],tl}; return; } int tm=(tl+tr)/2; build(v*2,tl,tm); build(v*2+1,tm+1,tr); if(t[v*2].ff>=t[v*2+1].ff){ t[v].ff=t[v*2].ff; t[v].ss=t[v*2].ss; } else{ t[v].ff=t[v*2+1].ff; t[v].ss=t[v*2+1].ss; } } pair <int,int> get(int v,int tl,int tr,int l,int r){ if(r<tl or tr<l)return {-1e18,0}; if(l<=tl && tr<=r) return t[v]; int tm=(tl+tr)/2; pair <int,int> p1=get(v*2,tl,tm,l,r); pair <int,int> p2=get(v*2+1,tm+1,tr,l,r); if(p1.ff>=p2.ff){ return p1; } else{ return p2; } } void rec(int l,int r){ if(l==r){ ok[l]=1; return; } pair <int,int> x=get(1,1,n,l,r); int ind=x.ss; int mx=x.ff; ok[ind]=1; int sum1=(sum[r]-sum[l-1])-(sum[r]-sum[ind-1]); int sum2=(sum[r]-sum[l-1])-(sum[ind]-sum[l-1]); if(sum1>=mx && l<=ind-1){ rec(l,ind-1); } if(sum2>=mx && ind+1<=r){ rec(ind+1,r); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } build(1,1,n); for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i]; } while(m--){ int u,v; cin>>u>>v; g[u].pb(v); g[v].pb(u); } rec(1,n); for(int i=1;i<=n;i++)cout<<ok[i]; } /* 4 4 2 2 4 3 1 2 1 3 2 3 3 4 4 3 4 2 2 1 1 2 3 2 4 1 10 9 10 9 8 7 4 4 3 2 1 1 1 2 1 3 2 4 3 5 5 7 5 8 7 9 8 10 3 6 1110101000 1 1 1 1 1 2 3 4 5 10 3 2 6 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...