Submission #15693

#TimeUsernameProblemLanguageResultExecution timeMemory
15693aintaHoliday (IOI14_holiday)C++98
100 / 100
1070 ms6624 KiB
#include"holiday.h" #include<algorithm> using namespace std; #define SZ 131072 #define N_ 100010 long long Res; struct A{ int a, num; bool operator <(const A &p)const{ return a < p.a; } }ord[N_]; struct ST{ long long Sum; int C; }IT[SZ*2+2]; int num[N_], N; void Ins(int node, int b, int e, int x, int ck){ if (b == e){ if (ck == IT[node].C)return; if (ck){ IT[node].C = 1; IT[node].Sum = ord[b].a; } else{ IT[node].C = 0, IT[node].Sum = 0; } return; } int m = (b + e) >> 1; if (x <= m)Ins(node * 2, b, m, x, ck); else Ins(node * 2 + 1, m + 1, e, x, ck); IT[node].Sum = IT[node * 2].Sum + IT[node * 2 + 1].Sum; IT[node].C = IT[node * 2].C + IT[node * 2 + 1].C; } long long Gap(int node, int x){ if (IT[node].C <= x)return IT[node].Sum; if (IT[node * 2 + 1].C >= x) return Gap(node * 2 + 1, x); else return IT[node * 2 + 1].Sum + Gap(node * 2, x - IT[node * 2 + 1].C); } void DP(int st, int b, int e, int s, int l, int d){ if (b > e)return; int m = (b + e) >> 1, i, t, x; long long M = 0, S; for (i = m; i <= e; i++) Ins(1, 0, SZ-1, num[i], 1); for (i = s; i <= l; i++){ Ins(1, 0, SZ-1, num[i], 1); t = d - st - i + m + m; if (t <= 0)break; S = Gap(1, t); if (M < S){ M = S, x = i; } } if (Res < M)Res = M; for (i = s; i <= l; i++)Ins(1, 0, SZ-1, num[i], 0); DP(st, b, m - 1, s, x, d); for (i = m; i <= e; i++)Ins(1, 0, SZ-1, num[i], 0); for (i = s; i < x; i++)Ins(1, 0, SZ-1, num[i], 1); DP(st, m + 1, e, x, l, d); for (i = s; i < x; i++)Ins(1, 0, SZ-1, num[i], 0); } void Do(int st, int d){ int i; DP(st, max(0, st - (d-1)/2), st, st, N - 1, d); } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { int i; N = n; for (i = 0; i < n; i++){ ord[i].a = attraction[i]; ord[i].num = i; } sort(ord, ord + n); for (i = 0; i < n; i++)num[ord[i].num] = i; Do(start, d); for (i = 0; i < n; i++)num[n - 1 - ord[i].num] = i; Do(n - 1 - start, d); return Res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...