Submission #175805

#TimeUsernameProblemLanguageResultExecution timeMemory
175805_EnkognitDivide and conquer (IZhO14_divide)C++14
100 / 100
341 ms11384 KiB
#include <bits/stdc++.h> #define ll long long #define mp make_pair #define pb push_back #define ld long double #define pll pair<ll,ll> #define y1 Enkognit #define fi first #define se second #define pld pair<ld,ld> using namespace std; const ll MOD=1000000007; ll l, r, n, m, k, y, leaf[10000001], a[1000001], x[1000001], b[1000001]; ll tt[10000001]; vector <ll> an; ll binpow(ll h,ll r) { ll l=1; while (r) { if (r&1) l*=h,l%=MOD; h*=h; h%=MOD; r/=2; } return l; } ll d[10000001]; void push(int h) { if (leaf[h]) return; if (tt[h]) { d[h*2]+=tt[h]; tt[h*2]+=tt[h]; d[h*2+1]+=tt[h]; tt[h*2+1]+=tt[h]; tt[h]=0; } } void build(int h,int l,int r) { if (l==r) {leaf[h]=1;d[h]=-1;return;} int w=(l+r)/2; build(h*2,l,w); build(h*2+1,w+1,r); d[h]=-1; } void update(int h,int l,int r,int x,int y,int k) { //cout << l << " " << x << " " << y << " " << r << "\n"; push(h); if (x>y) return; if (l==x && y==r) { d[h]+=k; tt[h]+=k; push(h); return; } int w=(l+r)/2; update(h*2,l,w,x,min(y,w),k); update(h*2+1,w+1,r,max(x,w+1),y,k); d[h]=max(d[h*2],d[h*2+1]); } ll get(int h,int l,int r) { push(h); if (l==r) return l; int w=(l+r)/2; if (d[h*2]>=0) return get(h*2,l,w); else return get(h*2+1,w+1,r); } int main() { //ios::sync_with_stdio(0); cin >> n; for (ll i = 1; i <= n; i++) { cin >> x[i] >> b[i] >> a[i]; b[i]+=b[i-1]; } ll ans=0; build(1,1,n); for (int i = 1; i <= n; i++) { update(1,1,n,i,i,1); //cout << i << "\n"; update(1,1,n,1,i,a[i]); update(1,1,n,1,i-1,x[i-1]-x[i]); ans=max(ans,b[i]-b[get(1,1,n)-1]); } cout << ans; return 0; } /* 4 0 5 1 1 7 2 4 4 1 7 15 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...