Submission #466705

#TimeUsernameProblemLanguageResultExecution timeMemory
466705Urvuk3Watering can (POI13_kon)C++17
0 / 100
515 ms16676 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int MAXN=3e5+5,MAXM=40,INF=1e9,MOD=1e9+7; #define fi first #define se second #define pll pair<ll,ll> #define pii pair<int,int> #define mid (l+r)/2 #define sz(a) int((a).size()) #define all(a) a.begin(),a.end() #define mod 1000000007LL #define pb push_back #define endl "\n" #define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush; #define PRINTBITS(x) {bitset<5> f=x; cerr<<#x<<'-'<<f<<endl<<flush;} #define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());} #define pb push_back #define pf push_front #define ppf pop_front #define ppb pop_back ll N,m,K,q,x,y,z,res=0,l,r; string s,t; vector<int> a; int lazy[4*MAXN]; pii seg1[4*MAXN]; // cuvacu par gde je druga vrdnost index maximuma int seg2[4*MAXN]; // cuvacu 1 u listu ako je drvo zrelo void propagate1(int node,int l,int r){ seg1[node].fi+=lazy[node]; if(l<r){ lazy[2*node]+=lazy[node]; lazy[2*node+1]+=lazy[node]; } lazy[node]=0; } void update1(int node,int l,int r,int L,int R,int val){ propagate1(node,l,r); if(l>r || l>R || r<L) return; if(L<=l && r<=R){ lazy[node]+=val; propagate1(node,l,r); return; } update1(2*node,l,mid,L,R,val); update1(2*node+1,mid+1,r,L,R,val); seg1[node].fi=max(seg1[2*node].fi,seg1[2*node+1].fi); } pii query1(int node,int l,int r,int L,int R){ propagate1(node,l,r); if(l>r || l>R || r<L) return {-INF,-INF}; if(L<=l && r<=R) return seg1[node]; return max(query1(2*node,l,mid,L,R),query1(2*node+1,mid+1,r,L,R)); } void update2(int node,int l,int r,int idx){ if(l==r){ seg2[node]++; return; } if(idx<=mid) update2(2*node,l,mid,idx); else update2(2*node+1,mid+1,r,idx); seg2[node]=seg2[2*node]+seg2[2*node+1]; } int query2(int node,int l,int r,int L,int R){ if(L<=l && r<=R) return seg2[node]; ll ret=0; if(L<=mid) ret+=query2(node,l,mid,L,R); if(R>mid) ret+=query2(node,mid+1,r,L,R); return ret; } void init(int node,int l,int r){ if(l==r){ seg1[node]={a[l],l}; seg2[node]=(a[l]>=K); return; } init(2*node,l,mid); } void inicjuj(int n, int k, int *D){ K=k; N=n; a.pb(INF); for(int i=1;i<=N;i++){ a.pb(D[i]); } init(1,1,N); } void podlej(int a, int b){ update1(1,1,N,a,b,1); while(true){ pii qu=query1(1,1,N,a,b); if(qu.fi<K) break; update2(1,1,N,qu.se); update1(1,1,N,qu.se,qu.se,-INF); } } int dojrzale(int a, int b){ return query2(1,1,N,a,b); }
#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...