oj.uz

Submission #126967

# Submission time Handle Problem Language Result Execution time Memory
126967 2019-07-08T17:12:26 Z ekrem Holiday (IOI14_holiday) C++
100 / 100
 2965 ms 27368 KB 
#include"holiday.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 200005
using namespace std;

typedef long long ll;
typedef pair < ll , ll > ii;

ll n, m, s, d, bas, son, ans, amk, a[N], ne[N], seg[4*N], say[4*N];
map < ll , ll > h, x;
map < ll , ll > :: iterator it;

void up(ll k, ll bas, ll son, ll x, ll y){
	if(bas == son){
		say[k] += y;
		seg[k] += y*ne[bas];
		return;
	}
	if(x <= orta)
		up(sol, bas, orta, x, y);
	else
		up(sag, orta + 1, son, x, y);
	say[k] = say[sol] + say[sag];
	seg[k] = seg[sol] + seg[sag];
}

ll qu(ll k, ll bas, ll son, ll x){
	if(bas == son)
		return min(x, say[k])*ne[bas];
	if(say[sag] <= x)
		return seg[sag] + qu(sol, bas, orta, x - say[sag]);
	return qu(sag, orta + 1, son, x);
}

void getir(ll bs, ll sn){
	// cout << "ofamk" << bs << " " << sn << endl;
	while(bas < bs){amk++;
		up(1, 1, m, x[a[bas]], -1);
		bas++;
	}
	while(bas > bs){amk++;
		bas--;
		up(1, 1, m, x[a[bas]], 1);
	}
	while(son > sn){amk++;
		up(1, 1, m, x[a[son]], -1);
		son--;
	}
	while(son < sn){amk++;
		son++;
		up(1, 1, m, x[a[son]], 1);
	}
}

void coz(ll bas, ll son, ll optl, ll optr){
	if(bas > son)return;
	ii mx = mp(0, optr);
	for(ll i = optl; i <= optr; i++){
		if(i > orta)
			break;
		ll k = d - ((orta - s) + (orta - i));
		if(k < 0)
			continue;
		getir(i, orta);
		mx = max(mx, mp(qu(1, 1, m, k), i));
	}
	ans = max(ans, mx.st);

	coz(bas, orta - 1, optl, mx.nd);
	coz(orta + 1, son, mx.nd, optr);
}

void cozz(){
	memset(seg, 0, sizeof seg);
	memset(say, 0, sizeof say);
	bas = 1; son = 0;
	for(int i = s; i <= n; i++){
		ll k = d - (i - s);
		if(k < 0)continue;
		up(1, 1, m, x[a[i]], 1);
		// getir(s, i);
		ans = max(ans, qu(1, 1, m, k));
	}
	memset(seg, 0, sizeof seg);
	memset(say, 0, sizeof say);
	bas = 1; son = 0;
	coz(s, n, 1, s);
}

ll findMaxAttraction(int nn, int ss, int dd, int aa[]){s = ss + 1;d = dd;n = nn;
	for(ll i = 1; i <= n; i++){
		a[i] = aa[i - 1];
		h[a[i]] = 1;
	}
	for(it = h.begin(); it != h.end(); it++){
		x[it->st] = ++m;
		ne[m] = it->st;
	}
	// for(ll i = 1; i <= m; i++)cout << ne[i] << " ";cout << endl;
	bas = son = 1;up(1, 1, m, x[a[1]], 1);

	cozz();
	reverse(a + 1, a + n + 1);
	s = n - s + 1;
	cozz();
	// cout << "AMK" << amk << endl;
	return ans;
}

// int main() {
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// 	ll n, start, d;
// 	int attraction[100000];
// 	ll i, n_s;
// 	n_s = scanf("%lld %lld %lld", &n, &start, &d);
// 	for (i = 0 ; i < n; ++i) {
// 	n_s = scanf("%d", &attraction[i]);
// 	}
// 	printf("%lld\n", findMaxAttraction((int)n, (int)start, (int)d,  attraction));
// 	return 0;
// }

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12892 KB Output is correct
2 Correct 16 ms 12792 KB Output is correct
3 Correct 18 ms 12792 KB Output is correct
4 Correct 18 ms 12920 KB Output is correct
5 Correct 16 ms 12892 KB Output is correct
6 Correct 17 ms 12792 KB Output is correct
7 Correct 16 ms 12896 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14056 KB Output is correct
2 Correct 37 ms 14064 KB Output is correct
3 Correct 45 ms 14064 KB Output is correct
4 Correct 43 ms 14044 KB Output is correct
5 Correct 123 ms 14072 KB Output is correct
6 Correct 54 ms 13304 KB Output is correct
7 Correct 81 ms 13412 KB Output is correct
8 Correct 86 ms 13560 KB Output is correct
9 Correct 43 ms 13048 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13304 KB Output is correct
2 Correct 17 ms 12920 KB Output is correct
3 Correct 22 ms 13304 KB Output is correct
4 Correct 41 ms 13200 KB Output is correct
5 Correct 38 ms 13176 KB Output is correct
6 Correct 20 ms 13048 KB Output is correct
7 Correct 19 ms 13048 KB Output is correct
8 Correct 20 ms 12920 KB Output is correct
9 Correct 19 ms 12924 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14072 KB Output is correct
2 Correct 490 ms 27368 KB Output is correct
3 Correct 471 ms 19320 KB Output is correct
4 Correct 35 ms 13304 KB Output is correct
5 Correct 20 ms 13048 KB Output is correct
6 Correct 20 ms 12920 KB Output is correct
7 Correct 19 ms 12920 KB Output is correct
8 Correct 2965 ms 25848 KB Output is correct
9 Correct 2880 ms 26744 KB Output is correct