제출 #299207

#제출 시각아이디문제언어결과실행 시간메모리
299207erd1휴가 (IOI14_holiday)C++14
0 / 100
17 ms1280 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define all(x) (x).begin(), (x).end() #define pb push_back typedef int64_t lld; typedef pair<int, int> pii; struct node{ node *L = 0, *R = 0; int key; lld sum; int val, cnt = 1; node(int v) : key(rand()), sum(v), val(v) { } void up(){ sum = val, cnt = 1; if(L)sum += L->sum, cnt += L->cnt; if(R)sum += R->sum, cnt += R->cnt; } pair<node*, node*> splitVal(int s){ if(val < s){ if(!L)return{nullptr, this}; auto p = L->splitVal(s); L = p.ss; up(); return {p.ff, this}; }else{ if(!R)return{this, nullptr}; auto p = R->splitVal(s); R = p.ff; up(); return {this, p.ss}; } } pair<node*, node*> splitSize(int k){ if(k == (L?L->cnt:0)){ auto x = L; L = 0; up(); return {x, this}; } else if(k < (L?L->cnt:0)){ //if(!L)return{nullptr, this}; auto p = L->splitSize(k); assert(p.ff->cnt == k); L = p.ss; up(); return {p.ff, this}; }else{ if(!R)return{this, nullptr}; auto p = R->splitSize(k-1-(L?L->cnt:0)); R = p.ff; up(); assert(cnt == k); return {this, p.ss}; } } friend node* merge(node* a, node* b){ if(!a)return b; if(!b)return a; if(a->key < b->key) return a->R = merge(a->R, b), a->up(), a; else return b->L = merge(a, b->L), b->up(), b; } } *root = 0; long long int findMaxAttraction(int n, int start, int d, int attraction[]) { srand(time(0)); lld ans = 0; for(int i = 0; i < min(n, d); i++){ if(!root)root = new node(attraction[i]); else{ auto p = root->splitVal(attraction[i]); root = merge(merge(p.ff, new node(attraction[i])), p.ss); } auto p = root->splitSize(d-i); assert(p.ff->cnt == min(i+1, d-i)); //cout << d-i << " " << p.ff->sum << endl; ans = max(ans, p.ff->sum); root = merge(p.ff, p.ss); } 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...