oj.uz

답안 #915606

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915606 2024-01-24T10:09:44 Z Trisanu_Das 휴가 (IOI14_holiday) C++17
100 / 100
 357 ms 64852 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 2 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2876 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 64128 KB Output is correct
2 Correct 86 ms 64068 KB Output is correct
3 Correct 98 ms 64084 KB Output is correct
4 Correct 85 ms 64080 KB Output is correct
5 Correct 89 ms 58972 KB Output is correct
6 Correct 26 ms 24668 KB Output is correct
7 Correct 51 ms 37224 KB Output is correct
8 Correct 60 ms 45424 KB Output is correct
9 Correct 17 ms 18268 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6236 KB Output is correct
2 Correct 4 ms 6264 KB Output is correct
3 Correct 4 ms 6244 KB Output is correct
4 Correct 7 ms 5980 KB Output is correct
5 Correct 8 ms 6100 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 64592 KB Output is correct
2 Correct 115 ms 64652 KB Output is correct
3 Correct 74 ms 35164 KB Output is correct
4 Correct 5 ms 5968 KB Output is correct
5 Correct 2 ms 3388 KB Output is correct
6 Correct 2 ms 3160 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 357 ms 64852 KB Output is correct
9 Correct 329 ms 64616 KB Output is correct