oj.uz

답안 #696327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696327 2023-02-06T08:45:51 Z vjudge1 휴가 (IOI14_holiday) C++14
100 / 100
 414 ms 63036 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,st,d,a[201000],T[201000]; 
ll su2[6010000];int su[6001000],c,ls[6001000],rs[6001000];
const int I=1e9;
void up(int &o,int lst,int l,int r,int x){
	o=++c;
	su2[o]=su2[lst]+x,su[o]=su[lst]+1,ls[o]=ls[lst],rs[o]=rs[lst];
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)up(ls[o],ls[lst],l,mid,x);
	else up(rs[o],rs[lst],mid+1,r,x);
}
ll kth(int o1,int o2,int l,int r,int k){
	if(l==r)return 1ll*min(su[o1]-su[o2],k)*l;
	int mid=(l+r)>>1,z=su[rs[o1]]-su[rs[o2]];
	if(k<=z)return kth(rs[o1],rs[o2],mid+1,r,k);
	return (su2[rs[o1]]-su2[rs[o2]])+kth(ls[o1],ls[o2],l,mid,k-z);
}
ll calc(int l,int r){
	int k=2*(r-st)+(st-l);
	if(k<d)return kth(T[r],T[l-1],0,I,d-k);
	return 0;
}
ll ans;
void cdq(int l,int r,int pl,int pr){
	if(l>r||pl>pr)return; 
	int ip=-1,mid=(l+r)>>1;
	ll M=-1;
	for(int i=pl;i<=pr;i++){
		ll V=calc(mid,i);
		if(M<V)M=V,ip=i;
	}
	ans=max(ans,M);
	cdq(l,mid-1,pl,ip),cdq(mid+1,r,ip,pr);
}
void sol(){
	c=0;
	for(int i=1;i<=n;i++)up(T[i],T[i-1],0,I,a[i]);
	cdq(1,st,st,n);
}
long long int findMaxAttraction(int N,int sta,int D,int attraction[]){
	n=N,st=sta+1,d=D;
	for(int i=1;i<=n;i++)a[i]=attraction[i-1];
	sol();
	st=n-st+1,reverse(a+1,a+n+1);sol();
	return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 692 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 62256 KB Output is correct
2 Correct 98 ms 62412 KB Output is correct
3 Correct 107 ms 62284 KB Output is correct
4 Correct 102 ms 62348 KB Output is correct
5 Correct 98 ms 57168 KB Output is correct
6 Correct 30 ms 17992 KB Output is correct
7 Correct 59 ms 32188 KB Output is correct
8 Correct 67 ms 38752 KB Output is correct
9 Correct 24 ms 13012 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2548 KB Output is correct
2 Correct 3 ms 2592 KB Output is correct
3 Correct 4 ms 2588 KB Output is correct
4 Correct 8 ms 2368 KB Output is correct
5 Correct 7 ms 2260 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 2 ms 1256 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 63036 KB Output is correct
2 Correct 119 ms 62876 KB Output is correct
3 Correct 94 ms 28620 KB Output is correct
4 Correct 6 ms 2388 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 414 ms 62824 KB Output is correct
9 Correct 375 ms 62776 KB Output is correct