Submission #510765

#TimeUsernameProblemLanguageResultExecution timeMemory
510765CodeTiger927Holiday (IOI14_holiday)C++14
0 / 100
124 ms65540 KiB
using namespace std; #include <iostream> #include <vector> #include <algorithm> #define MAXN 100005 pair<long long,int> add(pair<long long,int> a,pair<long long,int> b) { return make_pair(a.first + b.first,a.second + b.second); } struct node { node *lp,*rp; pair<long long,int> v; node(int l,int r) { lp = rp = nullptr; v = make_pair(0,0); if(l == r) return; int m = (l + r) >> 1; lp = new node(l,m); rp = new node(m + 1,r); } node(node *_lp,node *_rp) { lp = _lp; rp = _rp; v = add(lp -> v,rp -> v); } node(pair<long long,int> _v) { v = _v; } node* upd(int l,int r,int x,pair<long long,int> d) { if(l == r) return new node(add(v,d)); int m = (l + r) >> 1; if(x <= m) return new node(lp -> upd(l,m,x,d),rp); return new node(lp,rp -> upd(m + 1,r,x,d)); } pair<long long,int> get(int l,int r,int a,int b) { if(a > r || b < l) return make_pair(0,0); if(a <= l && b >= r) return v; int m = (l + r) >> 1; return add(lp -> get(l,m,a,b),rp -> get(m + 1,r,a,b)); } }; node* st[MAXN]; int N,S,D; pair<long long,int> dp[MAXN]; void solve1(int x,int y,int a,int b) { if(x > y) return; int z = (x + y) >> 1; dp[z] = {-1,-1}; for(int i = a;i <= b;++i) { int l = 0; int r = N - 1; while(l < r) { int m = (l + r + 1) >> 1; if(st[m] -> get(0,N - 1,z,i).second + (i - S) + (i - z) <= D) { l = m; }else{ r = m - 1; } } dp[z] = max(dp[z],{st[l] -> get(0,N - 1,z,i).first,i}); } if(x == y) return; solve1(x,z - 1,a,dp[z].second); solve1(z + 1,y,dp[z].second,b); } void solve2(int x,int y,int a,int b) { if(x > y) return; int z = (x + y) >> 1; if(!dp[z].first) dp[z] = {-1,-1}; for(int i = a;i <= b;++i) { int l = 0; int r = N - 1; while(l < r) { int m = (l + r + 1) >> 1; if(st[m] -> get(0,N - 1,i,z).second + (S - i) + (z - i) <= D) { l = m; }else{ r = m - 1; } } dp[z] = max(dp[z],{st[l] -> get(0,N - 1,i,z).first,i}); } if(x == y) return; solve2(z + 1,y,a,dp[z].second); solve2(x,z - 1,dp[z].second,b); } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { N = n; S = start; D = d; vector<pair<long long,int>> v; for(int i = 0;i < N;++i) { v.push_back({-attraction[i],i}); } st[0] = new node(0,N - 1); sort(v.begin(),v.end()); for(int i = 0;i < N;++i) { st[i + 1] = st[i] -> upd(0,N - 1,v[i].second,make_pair(-v[i].first,1)); } solve1(0,S,S,N - 1); solve2(S,N - 1,0,S); long long ans = 0; for(int i = 0;i < N;++i) { ans = max(ans,dp[i].first); } 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...