제출 #586669

#제출 시각아이디문제언어결과실행 시간메모리
586669SeDunion휴가 (IOI14_holiday)C++17
24 / 100
5042 ms4940 KiB
#include"holiday.h" #include<algorithm> #include<iostream> #include<vector> #include<set> using namespace std; using ll = long long; const int N = 1e5 + 123; int n; #define cout if(false)cout pair<int,int>pp[N]; int cnt[N << 2]; ll sum[N << 2]; void upd(int pos, int type, int l = 0, int r = n, int v = 1) { if (r - l == 1) { cnt[v] += type, sum[v] += type * pp[l].first; return; } int m = (l + r) >> 1; if (pos < m) upd(pos, type, l, m, v << 1); else upd(pos, type, m, r, v<<1|1); cnt[v] = cnt[v << 1] + cnt[v<<1|1]; sum[v] = sum[v << 1] + sum[v<<1|1]; } ll get(int &y, int l = 0, int r = n, int v = 1) { if (!y || !cnt[v]) return 0; if (cnt[v] <= y) { y -= cnt[v]; return sum[v]; } int m = (l + r) >> 1; ll res = get(y, m, r, v<<1|1); res += get(y, l, m, v << 1); return res; } int pos[N]; ll ans; int start, d; void solve(int l, int r, int opl, int opr) { if (l > r) return; int m = (l + r) >> 1; int opm = -1; cout << "---\n"; for (int i = m ; i < opl ; ++ i) { upd(pos[i], 1); cout << "add " << i << " " << pp[pos[i]].first << endl; } int x = d - (start - m); ll cur = 0; cout << m << " " << x << " m\n"; opm = opl; for (int i = opl ; i <= opr ; ++ i) { upd(pos[i], 1); cout << "add " << i << " " << pp[pos[i]].first << endl; int y = x - (i - m); if (y >= 0) { cout << i << " " << m << " " << y; ll temp = get(y); cout << " " << temp << endl; if (temp > cur) { opm = i; cur = temp; } } } for (int i = m ; i <= opr ; ++ i) { upd(pos[i], -1); } cout << m << " " << cur << endl; ans = max(ans, cur); solve(l, m - 1, opl, opm); solve(m + 1, r, opm, opr); } ll findMaxAttraction(int n_, int start_, int d_, int attraction[]) { n = n_, start = start_, d = d_; for (int i = 0 ; i < n ; ++ i) { pp[i] = {attraction[i], i}; } sort(pp, pp + n); for (int i = 0 ; i < n ; ++ i) { cout << pp[i].first << " "; } cout << endl; for (int i = 0 ; i < n ; ++ i) { pos[pp[i].second] = i; } for (int _ = 0 ; _ < 2 ; ++ _) { cout << "\n"; for (int i = 0 ; i < n ; ++ i) { cout << attraction[i] << " "; } cout << endl; solve(0, start, start, n - 1); for (int i = 0 ; i < n ; ++ i) { pp[i].second = n - pp[i].second - 1; pos[pp[i].second] = i; } reverse(attraction, attraction + n); start = n - start - 1; } 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...