oj.uz

답안 #59222

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59222 2018-07-21T08:34:00 Z Just_Solve_The_Problem 휴가 (IOI14_holiday) C++17
100 / 100
 1814 ms 18420 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()

const int N = (int)1e5 + 7;

struct T {
	ll sum;
	int cnt;
	T() {
		sum = cnt = 0;
	}
};
int nn;

struct TT {
	T tree[N * 4];
	void upd(int pos, int val, int v = 1, int l = 0, int r = nn) {
		if (l == r) {
			if (val == -1) {
				tree[v].sum = 0;
				tree[v].cnt = 0;
			} else {
				tree[v].sum = val;
				tree[v].cnt = 1;
			}
			return ;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) {
			upd(pos, val, v + v, l, mid);
		} else {
			upd(pos, val, v + v + 1, mid + 1, r);
		}
		tree[v].sum = tree[v + v].sum + tree[v + v + 1].sum;
		tree[v].cnt = tree[v + v].cnt + tree[v + v + 1].cnt;
	}
	ll get(int take, int v = 1, int l = 0, int r = nn) {
		if (l == r) {
			if (take > 0) {
				return tree[v].sum;
			} else {
				return 0;
			}
		}
		int mid = (l + r) >> 1;
		if (tree[v + v + 1].cnt >= take) {
			return get(take, v + v + 1, mid + 1, r);
		} else {
			return get(take - tree[v + v + 1].cnt, v + v, l, mid) + tree[v + v + 1].sum;
		}
	}
};
TT tr;

vector < ll > a, b, A, B, a1, b1;
ll c[5][N * 3];

bool cmpa(int x, int y) {
	return A[x] < A[y];
}

bool cmpb(int x, int y) {
	return B[x] < B[y];
}

void divide(int id, int l, int r, int optl, int optr) {
	if (l > r) return ;
	int opt = optl;
	ll best = -1;
	int mid = (l + r) >> 1;
	for (int i = optl; i <= optr; i++) {
		if (id <= 2) {
			tr.upd(a1[i], A[i]);
		} else {
			tr.upd(b1[i], B[i]);
		}
		ll cost;
		if (id & 1 ^ 1) {
			cost = tr.get(mid - 2 * (i + 1));
		} else {
			cost = tr.get(mid - (i + 1));
		}
		if (cost > best) {
			best = cost;
			opt = i;
		}
	}
	if (id <= 2) {
		for (int i = opt; i <= optr; i++) {
			tr.upd(a1[i], -1);
		}
	} else {
		for (int i = opt; i <= optr; i++) {
			tr.upd(b1[i], -1);
		}
	}
	divide(id, mid + 1, r, opt, optr);
	
	if (id <= 2) {
		for (int i = optl; i <= opt; i++) {
			tr.upd(a1[i], -1);
		}
	} else {
		for (int i = optl; i <= opt; i++) {
			tr.upd(b1[i], -1);
		}
	}
	divide(id, l, mid - 1, optl, opt);
	c[id][mid] = max(best, c[id][mid]);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	nn = n;
	for (int i = 0; i < n; i++) {
		if (i < start) {
			A.pb(attraction[i]);
			a.pb(i);
		} else if (i > start) {
			B.pb(attraction[i]);
			b.pb(i - start - 1);
		}
	}
	reverse(all(A));
	sort(all(a), cmpa);
	sort(all(b), cmpb);
	a1.resize(n);
	b1.resize(n);
	for (int i = 0; i < sz(a); i++)
		a1[a[i]] = i;
	for (int i = 0; i < sz(b); i++)
		b1[b[i]] = i;
	if (!a.empty()) {
		divide(1, 1, d, 0, sz(a) - 1);
		divide(2, 1, d, 0, sz(a) - 1);
	}
	if (!b.empty()) {
		divide(3, 1, d, 0, sz(b) - 1);
		divide(4, 1, d, 0, sz(b) - 1);
	}
	ll ans = 0;
	for (int i = 0; i < d; i++) {
		ans = max(ans, c[2][i] + attraction[start] + c[3][d - i - 1]);
		ans = max(ans, c[1][d - i - 1] + attraction[start] + c[4][i]);
		ans = max(ans, c[2][i] + c[3][d - i]);
		ans = max(ans, c[1][d - i] + c[4][i]);
	}
	ans = max(ans, c[2][d] + c[3][0]);
	ans = max(ans, c[1][0] + c[4][d]);
	return ans;
}

Compilation message

holiday.cpp: In function 'void divide(int, int, int, int, int)':
holiday.cpp:85:10: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   if (id & 1 ^ 1) {
       ~~~^~~
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 6520 KB Output is correct
2 Correct 9 ms 6800 KB Output is correct
3 Correct 7 ms 6800 KB Output is correct
4 Correct 7 ms 6800 KB Output is correct
5 Correct 8 ms 6932 KB Output is correct
6 Correct 9 ms 6936 KB Output is correct
7 Correct 7 ms 6964 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1308 ms 14244 KB Output is correct
2 Correct 1224 ms 14540 KB Output is correct
3 Correct 1158 ms 14688 KB Output is correct
4 Correct 1289 ms 14832 KB Output is correct
5 Correct 1814 ms 14832 KB Output is correct
6 Correct 535 ms 14832 KB Output is correct
7 Correct 969 ms 14832 KB Output is correct
8 Correct 1112 ms 14832 KB Output is correct
9 Correct 367 ms 14832 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 14832 KB Output is correct
2 Correct 28 ms 14832 KB Output is correct
3 Correct 26 ms 14832 KB Output is correct
4 Correct 28 ms 14832 KB Output is correct
5 Correct 34 ms 14832 KB Output is correct
6 Correct 14 ms 14832 KB Output is correct
7 Correct 16 ms 14832 KB Output is correct
8 Correct 13 ms 14832 KB Output is correct
9 Correct 13 ms 14832 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1196 ms 17584 KB Output is correct
2 Correct 1116 ms 18388 KB Output is correct
3 Correct 497 ms 18388 KB Output is correct
4 Correct 23 ms 18388 KB Output is correct
5 Correct 13 ms 18388 KB Output is correct
6 Correct 11 ms 18388 KB Output is correct
7 Correct 13 ms 18388 KB Output is correct
8 Correct 1720 ms 18388 KB Output is correct
9 Correct 1577 ms 18420 KB Output is correct