| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 837135 | aaronkim00 | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
const ll MOD = 998244353;
struct NODE{
int cnt, l, r;
ll sum;
};
int N, start, D, days;
vector<ll> arr;
vector<ll> A;
int nodeN;
NODE seg1[2000010];
int seg2[1200010];
int roots[100010];
ll decomp[100010];
void init2(int x, int s, int e){
if(s==e){
seg2[x] = 1;
}
else{
seg2[x] = 0;
int m = (s+e)/2;
init2(x*2, s, m);
init2(x*2+1, m+1, e);
}
}
void propagate2(int x){
if(seg2[x]){
seg2[x*2] = seg2[x];
seg2[x*2+1] = seg2[x];
seg2[x] = 0;
}
}
int query2(int x, int s, int e, int f){
if(s==e){
return seg2[x];
}
propagate2(x);
int m = (s+e)/2;
if(f<=m){
return query2(x*2, s, m, f);
}
else{
return query2(x*2+1, m+1, e, f);
}
}
void update2(int x, int s, int e, int fs, int fe, int v){
if(fe<s||e<fs){
return;
}
if(fs<=s&&e<=fe){
seg2[x] = v;
return;
}
propagate2(x);
int m = (s+e)/2;
update2(x*2, s, m, fs, fe, v);
update2(x*2+1, m+1, e, fs, fe, v);
}
void init1(int x, int s, int e){
seg1[x].cnt = seg1[x].sum = 0;
nodeN = max(nodeN, x);
if(s!=e){
seg1[x].l = x*2;
seg1[x].r = x*2+1;
int m = (s+e)/2;
init1(x*2, s, m);
init1(x*2+1, m+1, e);
}
}
ll query1(int x, int s, int e, int a, int b){
//printf("%d %d %d %d %d %lld\n", s, e, a, b, seg1[x].cnt, seg1[x].sum);
if(a==1&&b==seg1[x].cnt){
return seg1[x].sum;
}
if(s==e){
printf("%d %d %d %d %d %lld\n", s, e, a, b, seg1[x].cnt, seg1[x].sum);
printf("hello\n");
}
int m = (s+e)/2;
ll result = 0;
if(seg1[seg1[x].l].cnt >= a){
result += query1(seg1[x].l, s, m, a, min(b, seg1[seg1[x].l].cnt));
}
if(seg1[seg1[x].l].cnt < b){
result += query1(seg1[x].r, m+1, e, max(1, a-seg1[seg1[x].l].cnt), b-seg1[seg1[x].l].cnt);
}
return result;
}
void update1(int x, int s, int e, int f, ll v){
//printf("--------- %d %d %d %d %lld\n", x, s, e, f, v);
seg1[x].cnt++;
seg1[x].sum += v;
if(s!=e){
int m = (s+e)/2;
if(f<=m){
seg1[++nodeN] = seg1[seg1[x].l];
seg1[x].l = nodeN;
update1(nodeN, s, m, f, v);
}
else{
seg1[++nodeN] = seg1[seg1[x].r];
seg1[x].r = nodeN;
update1(nodeN, m+1, e, f, v);
}
}
}
vector<ll> oneWay(){
int M = A.size()-1;
if(M==0){
vector<ll> result(D+1);
return result;
}
nodeN = 0;
init1(1, 1, N);
init2(1, 1, D);
roots[0] = 1;
for(int i=1; i<=M; i++){
roots[i] = ++nodeN;
seg1[roots[i]] = seg1[roots[i-1]];
update1(roots[i], 1, N, A[i], decomp[A[i]]);
}
for(int i=2; i<=M; i++){
int left = i, right = D, mid = (left+right)/2;
while(left<right){
int t = query2(1, 1, D, mid);
if((2*i-1<=mid || query1(roots[t], 1, N, max(2*t-mid, 1), 2*t-mid+1) < decomp[A[i]])){
right = mid;
}
else{
left = mid+1;
}
mid = (left+right)/2;
}
update2(1, 1, D, mid, D, i);
}
vector<ll> result;
result.push_back(0);
for(int i=1; i<=D; i++){
int t = query2(1, 1, D, i);
result.push_back(query1(roots[t], 1, N, max(2*t-i, 1), t));
}
return result;
}
vector<ll> roundTrip(){
int M = A.size()-1;
if(M==0){
vector<ll> result(D+1);
return result;
}
nodeN = 0;
init1(1, 1, N);
init2(1, 1, D);
roots[0] = 1;
for(int i=1; i<=M; i++){
roots[i] = ++nodeN;
seg1[roots[i]] = seg1[roots[i-1]];
update1(roots[i], 1, N, A[i], decomp[A[i]]);
}
for(int i=2; i<=M; i++){
int left = 2*i-1, right = D, mid = (left+right)/2;
while(left<right){
int t = query2(1, 1, D, mid);
if((3*i-2<=mid || query1(roots[t], 1, N, max(3*t-mid-1, 1), 3*t-mid+1) < decomp[A[i]])){
right = mid;
}
else{
left = mid+1;
}
mid = (left+right)/2;
}
update2(1, 1, D, mid, D, i);
}
vector<ll> result;
result.push_back(0);
result.push_back(0);
result.push_back(0);
for(int i=1; i<=D; i++){
int t = query2(1, 1, D, i);
result.push_back(query1(roots[t], 1, N, max(3*t-i-1, 1), t));
}
return result;
}
vector<pair<ll, int> > temp;
int main(void){
scanf("%d %d %d", &N, &start, &days);
for(int i=0; i<N; i++){
ll x;
scanf("%lld", &x);
arr.push_back(x);
temp.push_back({x, i});
}
D = 3*N;
sort(all(temp));
for(int i=0; i<N; i++){
arr[temp[i].second] = i+1;
decomp[i+1] = temp[i].first;
}
vector<ll> r1, r2, r3, r4;
A.push_back(0);
for(int i=start; i>=0; i--){
A.push_back(arr[i]);
}
r1 = oneWay();
A.clear();
A.push_back(0);
for(int i=start-1; i>=0; i--){
A.push_back(arr[i]);
}
r2 = roundTrip();
A.clear();
A.push_back(0);
for(int i=start+1; i<N; i++){
A.push_back(arr[i]);
}
r3 = roundTrip();
A.clear();
A.push_back(0);
for(int i=start; i<N; i++){
A.push_back(arr[i]);
}
r4 = oneWay();
ll result = 0;
for(int i=0; i<=days; i++){
result = max(result, r1[i]+r3[days-i]);
result = max(result, r2[i]+r4[days-i]);
}
printf("%lld\n", result);
}