제출 #771828

#제출 시각아이디문제언어결과실행 시간메모리
771828Magikarp4000휴가 (IOI14_holiday)C++17
47 / 100
5072 ms10988 KiB
#include "holiday.h" #include <bits/stdc++.h> using namespace std; #define OPTM ios_base::sync_with_stdio(0); cin.tie(0); #define INF int(1e9+7) #define ln '\n' #define ll long long #define ull unsigned long long #define ui unsigned int #define us unsigned short #define FOR(i,s,n) for (int i = s; i < n; i++) #define FORR(i,n,s) for (int i = n; i > s; i--) #define FORX(u, arr) for (auto u : arr) #define PB push_back #define in(v,x) (v.find(x) != v.end()) #define F first #define S second #define PII pair<int, int> #define PLL pair<ll, ll> #define UM unordered_map #define US unordered_set #define PQ priority_queue #define ALL(v) v.begin(), v.end() const ll LLINF = 1e18+1; #define int long long struct Node { int x,cnt; }; const int MAXN = 1e5+1; int n,d; int a[MAXN]; Node st[MAXN*4+10]; vector<PII> v; int perm[MAXN]; void update(int s, int tl, int tr, int idx, int val) { if (tl == tr) { if (val == -1) { st[s].x = 0LL; st[s].cnt = 0; } else { st[s].x = val; st[s].cnt = 1; } } else { int tm = (tl+tr)/2; if (idx <= tm) update(s*2,tl,tm,idx,val); else update(s*2+1,tm+1,tr,idx,val); st[s].x = st[s*2].x+st[s*2+1].x; st[s].cnt = st[s*2].cnt+st[s*2+1].cnt; } } int query(int s, int tl, int tr, int l, int r, int t) { if (l <= tl && r >= tr) return t == 0 ? st[s].x : st[s].cnt; else { int tm = (tl+tr)/2; int cur = 0LL; if (l <= tm) cur += query(s*2,tl,tm,l,r,t); if (r > tm) cur += query(s*2+1,tm+1,tr,l,r,t); return cur; } } int walk(int s, int tl, int tr, int val) { if (tl == tr) return tl; int tm = (tl+tr)/2; if (query(1,0,n-1,tm+1,n-1,1) >= val) return walk(s*2+1,tm+1,tr,val); else return walk(s*2,tl,tm,val); } long long findMaxAttraction(int32_t N, int32_t start, int32_t D, int32_t A[]) { n = N, d = D; FOR(i,0,n) { a[i] = A[i]; v.PB({a[i],i}); } sort(ALL(v)); FOR(i,0,n) perm[v[i].S] = i; int res = 0LL; FOR(i,0,start+1) { FOR(j,i,start+1) update(1,0,n-1,perm[j],a[j]); FOR(j,start,n) { update(1,0,n-1,perm[j],a[j]); int used = (j-i) + min(j-start, start-i); int idx = walk(1,0,n-1,d-used); // cout << i << " " << j << " " << idx << ": "; // FOR(k,0,n) cout << query(1,0,n-1,k,k,0) << " "; // cout << ln; res = max(res, query(1,0,n-1,idx,n-1,0)); } FOR(j,0,n*4+10) st[j].x = st[j].cnt = 0LL; } 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...