oj.uz

답안 #70880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70880 2018-08-23T15:00:29 Z alenam0161 휴가 (IOI14_holiday) C++17
100 / 100
 552 ms 60016 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define Rl Root[rt].l
#define Rr Root[rt].r
#define Ll Root[lt].l
#define Lr Root[lt].r
const int N = 1e5+7;
int n,start,d,a[N],cnt,t,main_Root[N];
struct node{
	int l,r,cnt;
	long long val;
}Root[N*30];
void build(int rt,int l,int r){
	Root[rt].cnt=0;Root[rt].val=0;
	if(l==r)return;
	int m=(l+r)/2;
	Rl=++cnt;
	Rr=++cnt;
	build(Rl,l,m);
	build(Rr,m+1,r);
}
void upd(int lt,int rt,int l,int r,long long pos,long long v2){
	Root[rt].cnt=Root[lt].cnt+1;
	Root[rt].val=Root[lt].val+v2;
//	cout<<"update  "<<rt<<" "<< l<<" "<<r<<" "<<pos<<" "<<v2<<" "<<Root[rt].cnt<<" "<<Root[rt].val<<endl;
	if(l==r)return;
	int m=(l+r)/2;
	if(m>=pos){
		Rl=++cnt;
		Rr=Lr;
		upd(Ll,Rl,l,m,pos,v2);
	}
	else {
		Rl=Ll;
		Rr=++cnt;
		upd(Lr,Rr,m+1,r,pos,v2);
	}
	if(Root[rt].val!=Root[Rl].val+Root[Rr].val){
		assert(0);
	}
}
long long get(int lt,int rt,int l,int r,long long k){
	if(k<=0)return 0;
	int opt=Root[rt].cnt-Root[lt].cnt;
	long long val=Root[rt].val-Root[lt].val;
	//cout<<lt<<" "<<rt<< " "<<l<<" "<<r<<" "<<opt<<" "<<val<<" "<<k<<endl;
	if(l==r){
		if(k<=opt){
			return (Root[rt].val-Root[lt].val)/(Root[rt].cnt-Root[lt].cnt)*k;
			assert(0);
		}
		return val;
	}
	long long optr=Root[Rr].cnt-Root[Lr].cnt;
	long long vr=Root[Rr].val-Root[Lr].val;
	int m=(l+r)/2;
	//cout<<optr<<" "<<vr<<" "<<k<<endl;
	if(optr>k){
		return get(Lr,Rr,m+1,r,k);
	}
	else{
		return 	vr+get(Ll,Rl,l,m,k-optr);
	}
}
long long ans=0;
void fnd_ans(int tl,int tr,int l,int r){
	if(tl>tr||l>r)return;
	int m=(l+r)/2;
	int bst=tr;
	long long cur=-1;
	//cout<<start<<" "<<tl<< " "<<tr<<" "<<l<<" "<<r<<endl;
	for(int i=tl;i<=tr;++i){
	//	cout<<i<<" "<<m<<" "<<d-m+i-min(start-i,m-start)<<endl;
		long long c=get(main_Root[i-1],main_Root[m],1,t,d-m+i-min(start-i,m-start));
	//	cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<endl;
	//	cout<<i<<" "<<m<<" "<<c<<endl;
		if(c>cur){
			cur=c;
			bst=i;
		}
	}
	ans=max(ans,cur);
	fnd_ans(tl,bst,l,m-1);
	fnd_ans(bst,tr,m+1,r);
}
map<int,int> how,wh;

long long int findMaxAttraction(int n, int startt, int d, int attraction[]) {
	::n=n,start=startt,::d=d;
	for(int i=0;i<n;++i)a[i]=attraction[i];
	for(int i=0;i<n;++i)wh[a[i]]++;
	for(auto to:wh){
		how[to.first]=++t;
	}
	main_Root[0]=++cnt;
//	cout<<"hi"<<endl;
	build(main_Root[0],1,t);
	//cout<<"end"<<endl;
	for(int i=1;i<=n;++i){
		main_Root[i]=++cnt;
		upd(main_Root[i-1],main_Root[i],1,t,how[a[i-1]],a[i-1]);
	}
//	cout<<t<<endl;
	start++;
	fnd_ans(1,start,start,n);
    return ans;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 3 ms 440 KB Output is correct
4 Correct 3 ms 444 KB Output is correct
5 Correct 3 ms 496 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 580 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 4164 KB Output is correct
2 Correct 23 ms 4456 KB Output is correct
3 Correct 22 ms 6992 KB Output is correct
4 Correct 22 ms 7140 KB Output is correct
5 Correct 63 ms 19308 KB Output is correct
6 Correct 18 ms 19308 KB Output is correct
7 Correct 36 ms 19308 KB Output is correct
8 Correct 42 ms 19308 KB Output is correct
9 Correct 15 ms 19308 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 19308 KB Output is correct
2 Correct 203 ms 59824 KB Output is correct
3 Correct 171 ms 59824 KB Output is correct
4 Correct 8 ms 59824 KB Output is correct
5 Correct 4 ms 59824 KB Output is correct
6 Correct 6 ms 59824 KB Output is correct
7 Correct 4 ms 59824 KB Output is correct
8 Correct 548 ms 59824 KB Output is correct
9 Correct 552 ms 60016 KB Output is correct