oj.uz

Submission #30516

# Submission time Handle Problem Language Result Execution time Memory
30516 2017-07-24T10:04:28 Z cdemirer Holiday (IOI14_holiday) C++14
100 / 100
 1199 ms 10856 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

typedef struct Node_ {
	int size;
	ll value;
	bool enabled;
} Node;
const int segsz = 262144;
const int offset = 131072;
Node seg[segsz];
#define left(x) ((x)*2)
#define right(x) ((x)*2+1)
#define parent(x) ((x)/2)

int N, D;
int St, I, J;
int segpos[100000];
int A[100000];
ll best = 0;
queue<pair<ii, ii> > Q;

int dist(int x) {
	return (x>St?x-St:St-x);
}

ll get(int x, int t) {
	if (t >= seg[x].size) return seg[x].value;
	int ls = seg[left(x)].size;
	int rs = seg[right(x)].size;
	ll a = get(left(x), min(t, ls));
	if (t > ls) {
		a += get(right(x), t-ls);
	}
	return a;
}
void update(int pos, bool en) {
	int x = pos+offset;
	seg[x].enabled = en;
	x = parent(x);
	while (x) {
		seg[x].size = 0;
		seg[x].value = 0;
		if (seg[left(x)].enabled) {
			seg[x].size += seg[left(x)].size;
			seg[x].value += seg[left(x)].value;
		}
		if (seg[right(x)].enabled) {
			seg[x].size += seg[right(x)].size;
			seg[x].value += seg[right(x)].value;
		}
		x = parent(x);
	}
}

void add(int pos) {
	update(segpos[pos], true);
}
void remove(int pos) {
	update(segpos[pos], false);
}

void calc() {
	ii iv_i = Q.front().first;
	ii iv_j = Q.front().second;
	Q.pop();
	int mid = (iv_i.first + iv_i.second)/2;
	//cerr << "Trying to find optimal j for " << mid << " in [" << iv_j.first << "," << iv_j.second << "]" << endl;
	ll bestval = 0;
	int optj = iv_j.first;

	// calculations

	while (J < iv_j.first) {
		J++;
		add(J);
	}
	while (I > mid) {
		I--;
		add(I);
	}
	while (J > iv_j.first) {
		remove(J);
		J--;
	}
	while (I < mid) {
		remove(I);
		I++;
	}
	
	while (J <= iv_j.second) {
		int t = D - (2 * dist(I) + dist(J));
		if (t <= 0) break;
		ll att = get(1, t);
		if (att > bestval) {
			bestval = att;
			optj = J;
		}
		if (J == iv_j.second) break;
		J++;
		add(J);
	}
	best = max(best, bestval);

	// end calculations

	if (mid > iv_i.first) {
		Q.push(mp( mp(iv_i.first, mid-1), mp(iv_j.first, optj) ));
	}
	if (mid < iv_i.second) {
		Q.push(mp( mp(mid+1, iv_i.second), mp(optj, iv_j.second) ));
	}
}

void func() {
	Q.push(mp( mp(0, St), mp(St, N-1)));
	while ( ! Q.empty() ) {
		calc();
	}
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {

	if (!d) return 0;
	if (d == 1) return attraction[start];

	for (int i = offset; i < segsz; i++) {
		seg[i].value = 0;
		seg[i].size = 1;
		seg[i].enabled = false;
	}
	for (int i = offset-1; i > 0; i--) {
		seg[i].enabled = true;
		seg[i].value = 0;
		seg[i].size = 0;
	}

	N = n;
	D = d;
	St = I = J = start;
	for (int i = 0; i < N; i++) A[i] = attraction[i];
	vii tmp;
	for (int i = 0; i < N; i++) {
		tmp.pb(mp(A[i], i));
	}
	sort(tmp.begin(), tmp.end());
	reverse(tmp.begin(), tmp.end());
	for (int i = 0; i < N; i++) {
		seg[i+offset].value = tmp[i].first;
		segpos[tmp[i].second] = i;
	}
	add(St);
	func();
	
	for (int i = offset; i < segsz; i++) {
		seg[i].value = 0;
		seg[i].size = 1;
		seg[i].enabled = false;
	}
	for (int i = offset-1; i > 0; i--) {
		seg[i].enabled = true;
		seg[i].value = 0;
		seg[i].size = 0;
	}
	reverse(A, A+N);
	I = J = St = N - St - 1;
	tmp.clear();
	for (int i = 0; i < N; i++) {
		tmp.pb(mp(A[i], i));
	}
	sort(tmp.begin(), tmp.end());
	reverse(tmp.begin(), tmp.end());
	for (int i = 0; i < N; i++) {
		seg[i+offset].value = tmp[i].first;
		segpos[tmp[i].second] = i;
	}
	add(St);
	func();

	return best;
}

Compilation message

holiday.cpp: In function 'll get(int, int)':
holiday.cpp:39:6: warning: unused variable 'rs' [-Wunused-variable]
  int rs = seg[right(x)].size;
      ^
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 9220 KB Output is correct
2 Correct 3 ms 9220 KB Output is correct
3 Correct 3 ms 9220 KB Output is correct
4 Correct 3 ms 9216 KB Output is correct
5 Correct 3 ms 9220 KB Output is correct
6 Correct 3 ms 9220 KB Output is correct
7 Correct 0 ms 9220 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 10856 KB Output is correct
2 Correct 309 ms 10852 KB Output is correct
3 Correct 343 ms 10852 KB Output is correct
4 Correct 303 ms 10856 KB Output is correct
5 Correct 423 ms 10852 KB Output is correct
6 Correct 99 ms 9684 KB Output is correct
7 Correct 199 ms 10072 KB Output is correct
8 Correct 263 ms 10212 KB Output is correct
9 Correct 73 ms 9692 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9356 KB Output is correct
2 Correct 6 ms 9356 KB Output is correct
3 Correct 9 ms 9360 KB Output is correct
4 Correct 16 ms 9364 KB Output is correct
5 Correct 16 ms 9356 KB Output is correct
6 Correct 3 ms 9216 KB Output is correct
7 Correct 6 ms 9220 KB Output is correct
8 Correct 3 ms 9224 KB Output is correct
9 Correct 9 ms 9220 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 10848 KB Output is correct
2 Correct 323 ms 10856 KB Output is correct
3 Correct 283 ms 10072 KB Output is correct
4 Correct 13 ms 9360 KB Output is correct
5 Correct 3 ms 9220 KB Output is correct
6 Correct 3 ms 9220 KB Output is correct
7 Correct 9 ms 9216 KB Output is correct
8 Correct 1199 ms 10840 KB Output is correct
9 Correct 973 ms 10836 KB Output is correct