Submission #716216

#TimeUsernameProblemLanguageResultExecution timeMemory
716216sofija6Watering can (POI13_kon)C++14
0 / 100
4067 ms22944 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 300010 using namespace std; int h[MAXN],m,K,N; struct seg_tree { struct element { int sum=0,maxx=0; }; vector<element> st; element neutral_element; vector<int> lazy; int no_operation=-1; void Init() { m=1; while (m<N) m <<= 1; st.resize(2*m+2); lazy.resize(2*m+2); } void Propagate(int x,int lx,int rx) { if (lazy[x]==no_operation) return; st[x].maxx+=lazy[x]; if (lx!=rx) { lazy[2*x]=lazy[x]; lazy[2*x+1]=lazy[x]; } else if (st[x].maxx>=K) st[x].sum=1; lazy[x]=no_operation; } void Add(int l,int r,int val,int x,int lx,int rx) { Propagate(x,lx,rx); if (lx>r || rx<l) return; if (lx>=l && rx<=r) { lazy[x]=val; Propagate(x,lx,rx); return; } ll mid=(lx+rx)/2; Add(l,r,val,2*x,lx,mid); Add(l,r,val,2*x+1,mid+1,rx); st[x]={st[2*x].sum+st[2*x+1].sum,max(st[2*x].maxx,st[2*x+1].maxx)}; } int Calc(int l,int r,int x,int lx,int rx) { Propagate(x,lx,rx); if (lx>r || rx<l) return 0; if (lx>=l && rx<=r && ((st[x].maxx>=K && st[x].sum==rx-lx+1) || st[x].maxx<K)) return st[x].sum; int mid=(lx+rx)/2; return Calc(l,r,2*x,lx,mid)+Calc(l,r,2*x+1,mid+1,rx); } }; seg_tree S; void inicjuj(int n, int k, int *D) { N=n; K=k; S.Init(); for (int i=0;i<n;i++) { h[i+1]=D[i]; S.Add(i+1,i+1,D[i],1,1,m); } } void podlej(int a, int b) { S.Add(a+1,b+1,1,1,1,m); } int dojrzale(int a, int b) { return S.Calc(a+1,b+1,1,1,m); }
#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...
#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...