Submission #30537

#TimeUsernameProblemLanguageResultExecution timeMemory
30537NikeforHoliday (IOI14_holiday)C++98
0 / 100
23 ms7920 KiB
#include "holiday.h" #include <bits/stdc++.h> #define max_n 1<<17 #define ll long long using namespace std; int n, d, start, L, R; ll res; pair<ll,int> segment[max_n<<1]; int id[max_n]; int ord[max_n]; int a[max_n]; ll get(int x) { int k = 1; ll sum = 0; while(x < max_n) { if(segment[k+k+1].second >= x) k = k+k+1; else { x -= segment[k+k+1].second; sum += segment[k+k+1].first; k>>=1; } } sum += (x > 0) * segment[k].first; return sum; } void add(int x) { segment[x+max_n] = make_pair(a[ord[x]],1); x+= max_n; x>>=1; for(;x>1;x>>=1) { segment[x].first = segment[x+x].first + segment[x+x+1].first; segment[x].second = segment[x+x].second + segment[x+x+1].second; } } void erase(int x) { segment[x+max_n] = make_pair(0,0); x+=max_n; x>>=1; for(;x>1;x>>=1) { segment[x].first = segment[x+x].first + segment[x+x+1].first; segment[x].second = segment[x+x].second + segment[x+x+1].second; } } void fix(int l, int r) { while(l>L) erase(id[L++]); while(r<R) erase(id[R--]); while(l<L) add(id[--L]); while(r>R) add(id[++R]); } bool cmp(int x, int y) { return a[x]<a[y]; } void solve(int l, int r, int sl, int sr) { if(l>r) return; int mid = (l+r)>>1; for(int i = sl; i<=sr; i++) { if(i>mid) break; fix(i,mid); ll tmp = get(d-(mid-i)-(mid-start)); res = max(res, tmp); } solve(l, mid-1, sl,sr); solve(mid+1,r,sl,sr); } void solveStart(void) { for(int i=1; i<=n; i++) ord[i] = i; sort(ord+1, ord+n+1, cmp); for(int i = 1; i <= n; i++) id[ord[i]] = i; L = 1; R = 0; memset(segment, 0, sizeof(segment)); for(int i = start; i <= n; i++) { add(id[i]); res = max(res, get(d - (i - start))); } memset(segment, 0, sizeof(segment)); solve(start, n, 1, start); } long long int findMaxAttraction(int N, int Start, int D, int attraction[]) { n = N, d = D, start = Start+1; for (int i = 0; i < N; ++i) { a[i+1] = attraction[i]; ord[i+1] = i+1; } solveStart(); reverse(a+1, a+n+1); solveStart(); start = n - start + 1; return res; }

Compilation message (stderr)

holiday.cpp: In function 'void add(int)':
holiday.cpp:28:11: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  segment[x+max_n] = make_pair(a[ord[x]],1);
           ^
holiday.cpp: In function 'void erase(int)':
holiday.cpp:37:11: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  segment[x+max_n] = make_pair(0,0);
           ^
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...