Submission #710938

#TimeUsernameProblemLanguageResultExecution timeMemory
710938ld_minh4354Stranded Far From Home (BOI22_island)C++17
15 / 100
362 ms57040 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define debug(x) cout<<#x<<": "<<x<<"\n" int n,m,s[200005],ans[200005],sums[200005],pref[200005]; vector<int> adj[200005]; bool vis[200005]; struct node { int s,e,m,val,lazy; node *l,*r; node(int S,int E) { s=S;e=E;m=(s+e)/2; lazy=0; if (s!=e) { l=new node(s,m); r=new node(m+1,e); val=l->val+r->val; } else val=1; } void propogate() { if (lazy==0) return; val=val+lazy * (e-s+1); if (s!=e) { l->lazy += lazy; r->lazy += lazy; } lazy=0; } void update(int S,int E,int V) { if (s==S and e==E) lazy+=V; else { if (E<=m) l->update(S,E,V); else if (S>=m+1) r->update(S,E,V); else { l->update(S,m,V); r->update(m+1,E,V); } l->propogate();r->propogate(); val=l->val+r->val; } } int query(int S,int E) { propogate(); if (s==S and e==E) return val; else if (E<=m) return l->query(S,E); else if (S>=m+1) return r->query(S,E); else return l->query(S,m) + r->query(m+1,E); } }*root; signed main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // freopen("input.000","r",stdin); // freopen("output.000","w",stdout); // srand((unsigned)time(NULL)); // rand() int i,j,x,pos,u,v; pair<int,int> p[200005]; queue<int> q; set<int> sl,sr; cin>>n>>m; for (i=1;i<n+1;i++) cin>>s[i]; // for (i=1;i<m+1;i++) // { // cin>>u>>v; // adj[u].pb(v); // adj[v].pb(u); // } pref[0]=0; for (i=1;i<n+1;i++) pref[i]=pref[i-1]+s[i]; for (i=1;i<n+1;i++) p[i]={-s[i],i}; sort(p+1,p+n+1); sr.insert(n+1);sl.insert(0); s[0]=s[n+1]=1e18; root=new node(1,n); for (j=1;j<n+1;j++) { pos=p[j].se; sr.insert(pos); x=*sr.upper_bound(pos); if (x>pos+1 and s[pos]>pref[x-1]-pref[pos]) root->update(pos+1, x-1, -1); sl.insert(-pos); x=*sl.upper_bound(-pos); x=-x; if (pos>x+1 and s[pos]>pref[pos-1]-pref[x]) root->update(x+1, pos-1, -1); } for (i=1;i<n+1;i++) ans[i]=max(0ll,root->query(i,i)); for (i=1;i<n+1;i++) cout<<ans[i]; }

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:82:16: warning: unused variable 'u' [-Wunused-variable]
   82 |  int i,j,x,pos,u,v;
      |                ^
island.cpp:82:18: warning: unused variable 'v' [-Wunused-variable]
   82 |  int i,j,x,pos,u,v;
      |                  ^
#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...