Submission #126959

#TimeUsernameProblemLanguageResultExecution timeMemory
126959ekremHoliday (IOI14_holiday)C++98
47 / 100
211 ms65540 KiB
#include"holiday.h" #include <bits/stdc++.h> #define st first #define nd second #define mp make_pair #define pb push_back #define sol (k+k) #define sag (k+k+1) #define orta ((bas+son)/2) #define coc g[node][i] #define mod 1000000007 #define inf 1000000009 #define N 1000005 using namespace std; typedef long long ll; typedef pair < ll , ll > ii; ll n, m, s, d, bas, son, ans, amk, a[N], ne[N], seg[4*N], say[4*N]; map < ll , ll > h, x; map < ll , ll > :: iterator it; queue < pair < ii , ii > > q; void up(ll k, ll bas, ll son, ll x, ll y){ if(bas == son){ // cout << ne[bas] << " geldi bidane" << " " << y << endl; say[k] += y; seg[k] += y*ne[bas]; return; } if(x <= orta) up(sol, bas, orta, x, y); else up(sag, orta + 1, son, x, y); say[k] = say[sol] + say[sag]; seg[k] = seg[sol] + seg[sag]; } ll qu(ll k, ll bas, ll son, ll x){ if(bas == son) return min(x, say[k])*ne[bas]; if(say[sag] <= x) return seg[sag] + qu(sol, bas, orta, x - say[sag]); return qu(sag, orta + 1, son, x); } void getir(ll bs, ll sn){ // cout << "ofamk" << bs << " " << sn << endl; while(bas < bs){amk++; up(1, 1, m, x[a[bas]], -1); bas++; } while(bas > bs){amk++; bas--; up(1, 1, m, x[a[bas]], 1); } while(son > sn){amk++; up(1, 1, m, x[a[son]], -1); son--; } while(son < sn){amk++; son++; up(1, 1, m, x[a[son]], 1); } } void coz(ll bas, ll son, ll optl, ll optr){ // cout << bas << " " << son << " " << optl << " " << optr << " -> "; // amk++;if(amk > 100)exit(0); // cout << bas<<" " << son << " " << optl << " " << optr << endl; if(bas > son)return; ii mx = mp(0, optr); for(ll i = optl; i <= optr; i++){ if(i > orta) break; ll k = d - ((orta - s) + (orta - i)); if(k < 0){ mx.nd = i; continue; } // cout << " gele " << i << " " << orta << endl; getir(i, orta); // cout << i << " " << orta << " den " << k << " tane -> " << qu(1, 1, m, k) << endl; mx = max(mx, mp(qu(1, 1, m, k), i)); } ans = max(ans, mx.st); // cout << mx.st<< " " << mx.nd << "\n" << bas << " " << orta - 1 << " " << optl << " " << mx.nd << endl; // cout << orta + 1 << " " << son << " " << mx.nd << " " << optr << endl; // if(bas <= orta - 1) // q.push(mp(mp(bas, orta - 1), mp(optl, mx.nd))); // if(orta + 1 <= son) // q.push(mp(mp(orta + 1, son), mp(mx.nd, optr))); coz(bas, orta - 1, optl, mx.nd); coz(orta + 1, son, mx.nd, optr); } void cozz(){ memset(seg, 0, sizeof seg); memset(say, 0, sizeof say); bas = 1; son = 0; for(int i = s; i <= n; i++){ ll k = d - (i - s); if(k < 0)continue; getir(s, i); ans = max(ans, qu(1, 1, m, k)); } memset(seg, 0, sizeof seg); memset(say, 0, sizeof say); bas = 1; son = 0; q.push(mp(mp(s, n), mp(1, s))); while(!q.empty()){ coz(q.front().st.st, q.front().st.nd, q.front().nd.st, q.front().nd.nd); q.pop(); } } ll findMaxAttraction(int nn, int ss, int dd, int aa[]){s = ss + 1;d = dd;n = nn; for(ll i = 1; i <= n; i++){ a[i] = aa[i - 1]; h[a[i]] = 1; } for(it = h.begin(); it != h.end(); it++){ x[it->st] = ++m; ne[m] = it->st; } // for(ll i = 1; i <= m; i++)cout << ne[i] << " ";cout << endl; bas = son = 1;up(1, 1, m, x[a[1]], 1); cozz(); reverse(a + 1, a + n + 1); s = n - s + 1; cozz(); // cout << "AMK" << amk << endl; return ans; } // int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // ll n, start, d; // int attraction[100000]; // ll i, n_s; // n_s = scanf("%lld %lld %lld", &n, &start, &d); // for (i = 0 ; i < n; ++i) { // n_s = scanf("%d", &attraction[i]); // } // printf("%lld\n", findMaxAttraction((int)n, (int)start, (int)d, attraction)); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...