| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 299198 | erd1 | 휴가 (IOI14_holiday) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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; }
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 {L, this};
}
else if(k < (L?L->cnt:0)){
if(!L)return{nullptr, this};
auto p = L->splitSize(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();
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));
long long int 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);
//cout << d-i << " " << p.ff->sum << endl;
ans = max(ans, p.ff->sum);
root = merge(p.ff, p.ss);
}
return ans;
}