제출 #285744

#제출 시각아이디문제언어결과실행 시간메모리
285744Kastanda휴가 (IOI14_holiday)C++11
23 / 100
241 ms5616 KiB
// M #include<bits/stdc++.h> #include"holiday.h" #define lc (id << 1) #define rc (lc ^ 1) #define md ((l + r) >> 1) using namespace std; typedef long long ll; const int N = 100005; int n, st, d, A[N], Id[N], C[N * 4]; ll SM[N * 4]; vector < int > U; ll MX; void AddSeg(int i, int val, int id = 1, int l = 0, int r = (int)U.size()) { C[id] += val; SM[id] += (ll)val * U[i]; if (r - l < 2) return ; if (i < md) AddSeg(i, val, lc, l, md); else AddSeg(i, val, rc, md, r); } ll GetSeg(int &k, int id = 1, int l = 0, int r = (int)U.size()) { if (k <= 0) return 0LL; if (C[id] <= k) return k -= C[id], SM[id]; if (r - l < 2) { ll rt = (ll)U[l] * k; k = 0; return rt; } return GetSeg(k, rc, md, r) + GetSeg(k, lc, l, md); } inline void Add(int i, int val) { AddSeg(Id[i], val); } ll Get(int k) { int kk = k; return GetSeg(kk); } void Solve(int l, int r, int le, int ri) { if (r < l) return ; int opt = -1; // [le, l) is added. for (int i = l; i <= md; i ++) Add(i, 1); ll Mx = 0; for (int i = le; i <= ri; i ++) { ll val = Get(d - (md - st + md - i)); if (Mx < val) Mx = val, opt = i; if (i < st) Add(i, -1); } MX = max(MX, Mx); // (ri, md] for (int i = opt; i <= ri; i ++) if (i < st) Add(i, 1); // [opt, md] Solve(md + 1, r, opt, ri); for (int i = le; i < opt; i ++) if (i < st) Add(i, 1); // [le, md] for (int i = l; i <= md; i ++) Add(i, -1); // [le, l) Solve(l, md - 1, le, opt); } ll findMaxAttraction(int _n, int _start, int _d, int attraction[]) { n = _n; st = _start; d = _d; for (int i = 0; i < n; i ++) A[i] = attraction[i], U.push_back(A[i]); sort(U.begin(), U.end()); U.resize(unique(U.begin(), U.end()) - U.begin()); for (int i = 0; i < n; i ++) Id[i] = lower_bound(U.begin(), U.end(), A[i]) - U.begin(); MX = 0; for (int w = 0; w <= 1; w ++) { // Adding [le, l) : for (int i = 0; i < st; i ++) Add(i, 1); Solve(st, n - 1, 0, st); for (int i = 0; i < st; i ++) Add(i, -1); reverse(A, A + n); reverse(Id, Id + n); st = n - 1 - st; } return MX; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...