oj.uz

답안 #64229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
64229 2018-08-03T14:09:39 Z mhnd 휴가 (IOI14_holiday) C++14
100 / 100
 4117 ms 16592 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 3e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

pair<ll,int> a[N];
int p[N],num[4*N],S,n;
ll seg[4*N],d1[N],d2[N];

void update(int n,int s,int e,int in,bool to){
	if(s > in || e < in)return;
	if(s == e){
		num[n] = to;
		seg[n] = 1ll * to * a[in].first;
		return;
	}
	update(n*2,s,(s+e)/2,in,to);
	update(n*2+1,(s+e)/2+1,e,in,to);
	num[n] = num[n*2] + num[n*2+1];
	seg[n] = seg[n*2] + seg[n*2+1];
}

ll get(int n,int rem){
	if(rem <= 0)return 0;
	if(rem >= num[n])return seg[n];
	return get(n*2,rem) + get(n*2+1,rem-num[2*n]);
}

void solve(int l,int r,int x,int y,int at,ll v[],int w){
	if(l > r || x > y)return;
	int cur = (l+r)/2;
	at = -1;
	v[cur] = -1;
	for(int i=x;i<=y;i++){
		update(1,1,n,p[i],1);
		ll ans = get(1,cur - w * abs(i-S));
		if(ans > v[cur]){
			v[cur] = ans;
			at = i;
		}
	}
	for(int i=at;i<=y;i++)update(1,1,n,p[i],0);
	solve(cur+1,r,at,y,-1,v,w);
	for(int i=x;i<=y;i++)update(1,1,n,p[i],0);
	solve(l,cur-1,x,at,-1,v,w);
}

void solve2(int l,int r,int x,int y,int at,ll v[],int w){
	if(l > r || x > y)return;
	int cur = (l+r)/2;
	at = -1;
	v[cur] = -1;
	for(int i=y;i>=x;i--){
		update(1,1,n,p[i],1);
		ll ans = get(1,cur - w * abs(i-S));
		if(ans > v[cur]){
			v[cur] = ans;
			at = i;
		}
	}
	for(int i=x;i<=at;i++)update(1,1,n,p[i],0);
	solve2(cur+1,r,x,at,at,v,w);
	for(int i=x;i<=y;i++)update(1,1,n,p[i],0);
	solve2(l,cur-1,at,y,at,v,w);
}

void clear(){
	for(int i=1;i<=n;i++)update(1,1,n,p[i],0);
}

long long int findMaxAttraction(int N, int start, int d, int att[]){
	S = start+1;
	n = N;
	for(int i=1;i<=n;i++)a[i] = {att[i-1],i};
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	for(int i=1;i<=n;i++)p[a[i].second]=i;
	ll ans = 0;
	solve(1,d,S,n,-1,d1,2);
	clear();
	solve2(1,d,1,S-1,-1,d2,1);
	clear();
	for(int i=0;i<=d;i++)ans = max(ans,d1[i]+d2[d-i]);
	memset(d1,0,sizeof(d1));
	memset(d2,0,sizeof(d2));
	solve(1,d,S+1,n,-1,d1,1);
	clear();
	solve2(1,d,1,S,-1,d2,2);
	clear();
	for(int i=0;i<=d;i++)ans = max(ans,d1[i]+d2[d-i]);
	return ans;
	cout << "WOW" << endl;
}

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 8 ms 4984 KB Output is correct
2 Correct 6 ms 5096 KB Output is correct
3 Correct 8 ms 5336 KB Output is correct
4 Correct 8 ms 5336 KB Output is correct
5 Correct 8 ms 5336 KB Output is correct
6 Correct 6 ms 5336 KB Output is correct
7 Correct 6 ms 5336 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2451 ms 11008 KB Output is correct
2 Correct 2693 ms 11288 KB Output is correct
3 Correct 2518 ms 11564 KB Output is correct
4 Correct 2751 ms 11672 KB Output is correct
5 Correct 3332 ms 11736 KB Output is correct
6 Correct 929 ms 11736 KB Output is correct
7 Correct 1641 ms 11736 KB Output is correct
8 Correct 1802 ms 11736 KB Output is correct
9 Correct 989 ms 11736 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 11736 KB Output is correct
2 Correct 68 ms 11736 KB Output is correct
3 Correct 68 ms 11736 KB Output is correct
4 Correct 54 ms 11736 KB Output is correct
5 Correct 47 ms 11736 KB Output is correct
6 Correct 21 ms 11736 KB Output is correct
7 Correct 19 ms 11736 KB Output is correct
8 Correct 16 ms 11736 KB Output is correct
9 Correct 19 ms 11736 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2371 ms 13648 KB Output is correct
2 Correct 2788 ms 14544 KB Output is correct
3 Correct 1292 ms 14544 KB Output is correct
4 Correct 38 ms 14544 KB Output is correct
5 Correct 19 ms 14544 KB Output is correct
6 Correct 17 ms 14544 KB Output is correct
7 Correct 18 ms 14544 KB Output is correct
8 Correct 4117 ms 15808 KB Output is correct
9 Correct 3956 ms 16592 KB Output is correct