Submission #643611

#TimeUsernameProblemLanguageResultExecution timeMemory
643611jiahngHoliday (IOI14_holiday)C++14
100 / 100
3054 ms47856 KiB
#include"holiday.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef pair<int,int> pi; typedef vector <int> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define maxn 300010 #define INF (ll)1e9 #define MOD 1000000007 typedef pair <vi, int> pvi; typedef pair <int,pi> ipi; typedef vector <pii> vpii; int N,D,S,A[maxn]; int disc[maxn], undisc[maxn]; int F[maxn],G[maxn]; struct node{ int s,e,m,val=0,num=0; node *l,*r; node(int ss,int ee){ s = ss; e = ee; m = (s + e) / 2; if (s != e){ l = new node(s,m); r = new node(m+1,e); } } void upd(int p,int v){ if (s == e){ val += undisc[s] * v; num += v; }else{ if (p > m) r->upd(p, v); else l->upd(p,v); val = l->val + r->val; num = l->num + r->num; } } int qry(int v){ if (s == e) return (v > 0) * val; if (r->num < v) return r->val + l->qry(v-r->num); else return r->qry(v); } void clear(){ val = num = 0; if (s != e){ l->clear(); r->clear(); } } }*root; int M; int Fval[maxn], Gval[maxn]; void dnc(int l,int r,int vl,int vr){ // root is at vl-1 if (l > r) return; int m = (l + r) / 2; F[m] = vl; int cur = -1; FOR(i,vl,vr){ // s to i root->upd(disc[i], 1); int val = root->qry(m - (i - S)); if (val > cur){ cur = val; F[m] = i; } } //cout << m << ' ' << cur << '\n'; Fval[m] = cur; FOR(i,F[m],vr) root->upd(disc[i], -1); dnc(m+1,r,F[m],vr); FOR(i,vl,F[m]-1) root->upd(disc[i], -1); dnc(l,m-1,vl,F[m]); } void backdnc(int l,int r,int vl,int vr){ // root is at vr+1 if (l > r) return; int m = (l + r) / 2; G[m] = vr; int cur = -1; DEC(i,vr,vl){ // i to s root->upd(disc[i], 1); int val = root->qry(m - (S-1 - i)); if (val > cur){ cur = val; G[m] = i; } } //cout << m << ' ' << Gval[m] << ' ' << cur << '\n'; Gval[m] = cur; FOR(i,vl,G[m]) root->upd(disc[i], -1); backdnc(m+1,r,vl,G[m]); FOR(i,G[m]+1,vr) root->upd(disc[i], -1); backdnc(l,m-1,G[m],vr); } int B[maxn]; int solve(){ vi v2; FOR(i,0,S) v2.pb(B[i]); FOR(i,S+1,N-1){v2.pb(0); v2.pb(B[i]);} // model return moves M = v2.size(); FOR(i,0,M-1) A[i] = v2[i]; vpi v; FOR(i,0,M-1) v.pb(pi(A[i], i)); sort(all(v)); FOR(i,0,M-1){ disc[v[i].s] = i; undisc[i] = v[i].f; } root->clear(); dnc(0, D, S, M-1); root->clear(); backdnc(0,D,0,S-1); int ans = max(Fval[D], Gval[D-1]); FOR(i,0,D){ // number of days spent going right if (D - i - 1 >= 0){ ans = max(ans, Gval[D - i -1] + Fval[i]); } } return ans; } ll findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) { N = n; D = d; S = start; root = new node(0,2*N-1); FOR(i,0,N-1) B[i] = attraction[i]; int ans = solve(); reverse(B, B+N); S = N - 1 - S; ans = max(ans, solve()); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...