oj.uz

답안 #1103012

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1103012 2024-10-19T11:21:19 Z alexander707070 휴가 (IOI14_holiday) C++14
23 / 100
 337 ms 14272 KB 
#include<bits/stdc++.h>
#include"holiday.h"

#define MAXN 500007
using namespace std;

int n,a[MAXN],start;

vector<int> w;
unordered_map<int,int> mp;
int ret[MAXN],cnt;

long long ans;

struct ST{
	pair<long long,int> tree[4*MAXN];

	void init(){
		for(int i=1;i<=4*cnt;i++){
			tree[i]={0,0};
		}
	}

	pair<long long,int> combine(pair<long long,int> fr,pair<long long,int> sc){
		return {fr.first+sc.first,fr.second+sc.second};
	}

	void update(int v,int l,int r,int pos,int val){
		if(l==r){
			tree[v].second+=val;
			tree[v].first+=ret[l]*val;
		}else{
			int tt=(l+r)/2;

			if(pos<=tt)update(2*v,l,tt,pos,val);
			else update(2*v+1,tt+1,r,pos,val);

			tree[v]=combine(tree[2*v],tree[2*v+1]);
		}
	}

	long long getsum(int v,int l,int r,long long k){
		if(k<0)return 0;

		if(l==r){
			if(tree[v].second<=k)return tree[v].first;
			return k*ret[l];
		}else{
			int tt=(l+r)/2;
			if(tree[2*v+1].second>=k){
				return getsum(2*v+1,tt+1,r,k);
			}else{
				return getsum(2*v,l,tt,k-tree[2*v+1].second) + tree[2*v+1].first;
			}
		}
	}
}seg;

long long pref[MAXN],suff[MAXN];

void solveopt_right(int dl,int dr,int optl,int optr){
	if(dl>dr)return;

	int mid=(dl+dr)/2,opt=optl;
	suff[mid]=0;

	for(int i=optl;i<=optr;i++){
		seg.update(1,1,cnt,a[i],1);

		long long curr=seg.getsum(1,1,cnt,mid-(i-start));
		if(curr>suff[mid]){
			suff[mid]=curr;
			opt=i;
		}
	}

	for(int i=optl;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);

	solveopt_right(dl,mid-1,optl,opt);

	for(int i=optl;i<opt;i++)seg.update(1,1,cnt,a[i],1);
	solveopt_right(mid+1,dr,opt,optr);

	for(int i=optl;i<opt;i++)seg.update(1,1,cnt,a[i],-1);
}

void solveopt_left(int dl,int dr,int optl,int optr){
	if(dl>dr)return;

	int mid=(dl+dr)/2,opt=optr;
	pref[mid]=0;

	for(int i=optr;i>=optl;i--){
		seg.update(1,1,cnt,a[i],1);

		long long curr=seg.getsum(1,1,cnt,mid-2*(start-1-i));
		if(curr>pref[mid]){
			pref[mid]=curr;
			opt=i;
		}
	}

	for(int i=optl;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
	
	solveopt_left(dl,mid-1,opt,optr);

	for(int i=opt+1;i<=optr;i++)seg.update(1,1,cnt,a[i],1);
	solveopt_left(mid+1,dr,optl,opt);

	for(int i=opt+1;i<=optr;i++)seg.update(1,1,cnt,a[i],-1);
}

long long int findMaxAttraction(int N, int st, int d, int attraction[]) {
//long long int findMaxAttraction(int N, int st, int d, vector<int> attraction) {
	n=N; start=st+1;

	for(int i=1;i<=n;i++){
		a[i]=attraction[i-1];
		w.push_back(a[i]);
	}

	sort(w.begin(),w.end());
	for(int i=0;i<w.size();i++){
		if(i==0 or w[i]!=w[i-1])cnt++;
		mp[w[i]]=cnt; ret[cnt]=w[i];
	}

	for(int i=1;i<=n;i++)a[i]=mp[a[i]];

	seg.init();
	solveopt_right(0,d,start,n);

	seg.init();
	solveopt_left(0,d,1,start-1);

	ans=max(ans,suff[d]);
	for(int i=0;i<=d-2;i++){
		ans=max(ans,pref[i]+suff[d-2-i]);
	}

	reverse(a+1,a+n+1);
	start=n-start+1;

	seg.init();
	solveopt_right(0,d,start,n);

	seg.init();
	solveopt_left(0,d,1,start-1);

	ans=max(ans,suff[d]);
	for(int i=0;i<=d-2;i++){
		ans=max(ans,pref[i]+suff[d-2-i]);
	}

    return ans;
}

/*int main(){

	cout<<findMaxAttraction(5,2,7,{10,2,20,30,1})<<"\n";

	return 0;
}*/

Compilation message

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:123:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for(int i=0;i<w.size();i++){
      |              ~^~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 9040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 14024 KB Output is correct
2 Correct 28 ms 14116 KB Output is correct
3 Correct 56 ms 14108 KB Output is correct
4 Correct 45 ms 14040 KB Output is correct
5 Correct 337 ms 14272 KB Output is correct
6 Correct 146 ms 13428 KB Output is correct
7 Correct 195 ms 13604 KB Output is correct
8 Correct 220 ms 13792 KB Output is correct
9 Correct 129 ms 13384 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 9040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 14024 KB Output isn't correct
2 Halted 0 ms 0 KB -