oj.uz

Submission #424900

# Submission time Handle Problem Language Result Execution time Memory
424900 2021-06-12T11:24:13 Z vanic Holiday (IOI14_holiday) C++14
100 / 100
 1159 ms 14444 KB 
#include "holiday.h"
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <iostream>

using namespace std;

typedef long long ll;

const int maxn=1e5+5, Log=17, pot=(1<<Log);


ll t[pot*2];
int br[pot*2];

int niz[maxn];
int pos[maxn];

bool cmp(int a, int b){
	return niz[a]>niz[b];
}


void update(int x){
	x+=pot;
	br[x]^=1;
	for(x/=2; x>0; x/=2){
		br[x]=br[x*2]+br[x*2+1];
		t[x]=0;
		if(br[x*2]){
			t[x]+=t[x*2];
		}
		if(br[x*2+1]){
			t[x]+=t[x*2+1];
		}
	}
}


ll query(int x, int broj){
//	cout << x << ' ' << broj << endl;
	if(broj<=0 || !br[x]){
		return 0;
	}
	if(br[x]<=broj){
		return t[x];
	}
	return query(x*2, broj)+query(x*2+1, broj-br[x*2]);
}

pair < int, ll > dp1[maxn*3];
pair < int, ll > dp2[maxn*3];
int pozicija[maxn];
int poc;

void rijesi1(int L, int D, int l, int d){
//	cout << L << ' ' << D << ' ' << l << ' ' << d << endl;
	if(L==D){
		return;
	}
	if(l>=d){
		return;
	}
	int mid=(l+d)/2;
	ll maksi=0;
	int ind=L;
	ll val;
	for(int i=L; i<D; i++){
		update(pozicija[i]);
		val=query(1, mid-(i-poc));
		if(maksi<val){
			maksi=val;
			ind=i;
		}
	}
	dp1[mid]={ind, maksi};
	for(int i=L; i<D; i++){
		update(pozicija[i]);
	}
	rijesi1(L, ind+1, l, mid);
	for(int i=L; i<ind; i++){
		update(pozicija[i]);
	}
	rijesi1(ind, D, mid+1, d);
	for(int i=L; i<ind; i++){
		update(pozicija[i]);
	}
}

void rijesi2(int L, int D, int l, int d){
//	cout << L << ' ' << D << ' ' << l << ' ' << d << endl;
	if(L==D){
		return;
	}
	if(l>=d){
		return;
	}
	int mid=(l+d)/2;
	ll maksi=0;
	int ind=D-1;
	ll val;
	for(int i=D-1; i>=L; i--){
		update(pozicija[i]);
		val=query(1, mid-(poc-i));
//		cout << val <<  endl;
		if(maksi<val){
			maksi=val;
			ind=i;
		}
	}
//	cout << mid << ' ' << ind << ' ' << maksi << endl;
//	cout << "poso" << endl;
	dp2[mid]={ind, maksi};
	for(int i=L; i<D; i++){
		update(pozicija[i]);
	}
	rijesi2(ind, D, l, mid);
	for(int i=D-1; i>ind; i--){
		update(pozicija[i]);
	}
	rijesi2(L, ind+1, mid+1, d);
	for(int i=D-1; i>ind; i--){
		update(pozicija[i]);
	}
}


ll findMaxAttraction(int n, int x, int d, int l[]){
	poc=x;
	for(int i=0; i<n; i++){
		niz[i]=l[i];
		pos[i]=i;
	}
	sort(pos, pos+n, cmp);
	for(int i=0; i<n; i++){
		t[i+pot]=niz[pos[i]];
		pozicija[pos[i]]=i;
	}

	rijesi1(x, n, 0, n*3);

	rijesi2(0, x, 0, n*3);

/*	for(int i=0; i<n*3; i++){
		cout << dp1[i].second << ' ';
	}
	cout << endl;
	for(int i=0; i<n*3;  i++){
		cout << dp2[i].second << ' ';
	}
	cout << endl;*/
	int druga;
	ll uk;
	ll sol=0;
	for(int i=0; i<=d; i++){
		druga=max(0, d-i-(dp1[i].first-x));
		uk=dp1[i].second+dp2[druga].second;
		sol=max(sol, uk);
		druga=max(0, d-i-(x-dp2[i].first));
		uk=dp2[i].second+dp1[druga].second;
		sol=max(sol, uk);
	}
	return sol;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 8944 KB Output is correct
2 Correct 563 ms 8944 KB Output is correct
3 Correct 940 ms 8892 KB Output is correct
4 Correct 652 ms 9028 KB Output is correct
5 Correct 942 ms 8416 KB Output is correct
6 Correct 259 ms 3140 KB Output is correct
7 Correct 502 ms 5096 KB Output is correct
8 Correct 616 ms 5908 KB Output is correct
9 Correct 187 ms 2460 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1076 KB Output is correct
2 Correct 24 ms 1048 KB Output is correct
3 Correct 28 ms 1096 KB Output is correct
4 Correct 25 ms 1016 KB Output is correct
5 Correct 25 ms 1100 KB Output is correct
6 Correct 9 ms 852 KB Output is correct
7 Correct 9 ms 844 KB Output is correct
8 Correct 10 ms 820 KB Output is correct
9 Correct 10 ms 844 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 13532 KB Output is correct
2 Correct 1148 ms 8956 KB Output is correct
3 Correct 461 ms 6916 KB Output is correct
4 Correct 24 ms 1060 KB Output is correct
5 Correct 9 ms 844 KB Output is correct
6 Correct 9 ms 816 KB Output is correct
7 Correct 11 ms 896 KB Output is correct
8 Correct 1159 ms 14444 KB Output is correct
9 Correct 1137 ms 14408 KB Output is correct