Submission #116091

#TimeUsernameProblemLanguageResultExecution timeMemory
116091someone_aaHoliday (IOI14_holiday)C++17
0 / 100
139 ms65536 KiB
#include "holiday.h" #include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const int maxn = 100100; ll value[maxn], d; ll arr[maxn]; class node { public: ll sum, cnt, lb, rb; node *leftchild, *rightchild; node(ll _sum, ll _cnt) { sum = _sum; cnt = _cnt; } node(node *a, node *b) { leftchild = a; rightchild = b; sum = a->sum + b->sum; cnt = a->cnt + b->cnt; } }; node* build(int li=1, int ri=d) { if(li == ri) return new node(0LL, 0LL); else { int mid = (li + ri) / 2; return new node(build(li, mid), build(mid+1, ri)); } } node* update(node *curr, ll uind, ll uval, int li=1, int ri=d) { if(li == ri) { return new node(curr->sum + uval, curr->cnt + 1); } else { int mid = (li + ri) / 2; if(uind <= mid) return new node(update(curr->leftchild, uind, uval, li, mid), curr->rightchild); else return new node(curr->leftchild, update(curr->rightchild, uind, uval, mid+1, ri)); } } ll solve(node *p, node *pm, ll k, int li=1, int ri=d) { ll total = p->cnt - pm->cnt; if(total < k) return (p->sum - pm->sum); if(li == ri) { return k * value[li]; } else { int mid = (li + ri) / 2; ll total_right = p->rightchild->cnt - pm->rightchild->cnt; if(total_right >= k) return solve(p->rightchild, pm->rightchild, k, mid+1, ri); else return (p->rightchild->sum - pm->rightchild->sum) + solve(p->leftchild, pm->leftchild, k - total, li, mid); } } node *prefix[maxn]; set<int>st; map<int,int>ind; long long int findMaxAttraction(int n, int start, int c, int attraction[]) { start++; for(int i=0;i<n;i++) { st.insert(attraction[i]); } int br = 1; for(int i:st) { value[br] = i; ind[i] = br++; } d = br - 1; for(int i=n-1;i>=0;i--) { arr[i+1] = ind[attraction[i]]; } node *curr = build(); prefix[0] = curr; for(int i=1;i<=n;i++) { curr = update(curr, arr[i], value[arr[i]]); prefix[i] = curr; } ll result = 0LL; for(int i=1;i<=start;i++) { for(int j=start;j<=n;j++) { ll walk = j - i + min(start - i, j - start); //cout<<i<<" - "<<j<<" walking: "<<walk<<"\n"; result = max(result, solve(prefix[j], prefix[i-1], c - walk)); } } return result; }

Compilation message (stderr)

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...