oj.uz

Submission #30519

# Submission time Handle Problem Language Result Execution time Memory
30519 2017-07-24T10:28:16 Z ozaslan Holiday (IOI14_holiday) C++14
100 / 100
 516 ms 7928 KB 
#include <bits/stdc++.h>
#include <string>
#include <utility>
#include <algorithm>
#include <stdio.h>
#include "holiday.h"
#define mp make_pair
#define ff first
#define ss second
#define ll long long
using namespace std;

const int max_N = 1 << 17;
int N, bas, g;
int d[max_N];
ll sonuc = 0;
pair<ll, int> st[max_N << 1];
int id[max_N], sira[max_N];

void ekle (int k) {
	st[k + max_N] = mp(d[sira[k]], 1);
	k += max_N;
	
	while(k > 1){
		k >>= 1;
		st[k] = mp(st[k+k].ff + st[k+k+1].ff, st[k+k].ss + st[k+k+1].ss);
	}
}

void sil (int k) {
	st[k + max_N] = mp(0, 0);
	k += max_N;
	while (k > 1) {
		k >>= 1;
		st[k] = mp(st[k+k].ff + st[k+k+1].ff, st[k+k].ss + st[k+k+1].ss);
	}
}

ll get (int k) {
	int x = 1;
	ll sonuc = 0;
//	printf("N: %d\n", N);
	while (x < max_N) {
	//	printf("x: %d\n", x);
		if (st[x+x+1].ss >= k)
			x = x+x+1;
		else {
			k -= st[x+x+1].ss;
			sonuc += st[x+x+1].ff;
			x = x+x;
		}
	}
	sonuc += (k > 0) * st[x].ff;
	return sonuc;
}

int bsol, bsag;

void fix (int sol, int sag) {
	while (bsag < sag) ekle (id[++bsag]);
	while (bsol > sol) ekle (id[--bsol]);
	while (bsag > sag) sil (id[bsag--]);
	while (bsol < sol) sil (id[bsol++]);
}

void coz (int sol, int sag, int oSol, int oSag) {
	//printf("Sol: %d, sag: %d, oSol: %d, oSag: %d\n", sol, sag, oSol, oSag);
	if (sol > sag) return;

	int o = (sol + sag) >> 1;
	ll eb = 0;
	ll opt = -1;
	for (int i = oSol; i <= o && i <= oSag; i++) {
		fix(i, o);
		ll s = get(g - (o - i) - (o - bas));
	//	printf("i: %d,  o: %d, s: %d\n", i, o, s);
		
		if (opt == -1 || s >= eb) {
			sonuc = max(sonuc, s);
			eb = s;
			opt = i;
		}
	}

	coz (sol, o-1, oSol, opt);
	coz (o+1, sag, opt, oSag);
}

bool cmp(int x, int y) {return d[x] < d[y];}

void cozBas() {
	for (int i = 1; i <= N; i++)
		sira[i] = i;

	sort (sira +1, sira + N +1, cmp);

	for (int i = 1; i <= N; i++)
		id[sira[i]] = i;

	bsol = 1;
	bsag = 0;

	memset(st, 0, sizeof st);

	for (int i = bas; i <= N; i++) {
		ekle(id[i]);
		sonuc = max(sonuc, get(g- (i - bas)) );
	}

	memset(st, 0, sizeof st);
	coz(bas, N, 1, bas);

}

long long int findMaxAttraction(int n, int start, int D, int attraction[]) {
	N = n;
	bas = start + 1;
	g = D;

	for (int i = 0; i < n; i++)
		d[i+1] = attraction[i];

	cozBas();
	reverse(d +1, d + n +1);
	bas = n - bas +1;
	cozBas();
	return sonuc;
}

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

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7924 KB Output is correct
2 Correct 106 ms 7924 KB Output is correct
3 Correct 106 ms 7920 KB Output is correct
4 Correct 113 ms 7920 KB Output is correct
5 Correct 153 ms 7928 KB Output is correct
6 Correct 39 ms 7924 KB Output is correct
7 Correct 83 ms 7924 KB Output is correct
8 Correct 96 ms 7920 KB Output is correct
9 Correct 36 ms 7924 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7920 KB Output is correct
2 Correct 3 ms 7928 KB Output is correct
3 Correct 3 ms 7928 KB Output is correct
4 Correct 9 ms 7920 KB Output is correct
5 Correct 9 ms 7928 KB Output is correct
6 Correct 0 ms 7924 KB Output is correct
7 Correct 3 ms 7928 KB Output is correct
8 Correct 3 ms 7924 KB Output is correct
9 Correct 3 ms 7924 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7920 KB Output is correct
2 Correct 106 ms 7924 KB Output is correct
3 Correct 183 ms 7924 KB Output is correct
4 Correct 6 ms 7928 KB Output is correct
5 Correct 3 ms 7924 KB Output is correct
6 Correct 3 ms 7920 KB Output is correct
7 Correct 3 ms 7924 KB Output is correct
8 Correct 453 ms 7924 KB Output is correct
9 Correct 516 ms 7928 KB Output is correct