Submission #82413

#	Time	Username	Problem	Language	Result	Execution time	Memory
82413		faceless	Homecoming (BOI18_homecoming)	C++14	0 / 100	41 ms	8672 KiB

homecoming

#include <bits/stdc++.h>
#include <homecoming.h>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 3e4 + 10;
const int block = 320;
const int inf = 1e9;

int n, k, a[maxn], b[maxn];
int lazy[4 * maxn], sec[4 * maxn];
pair <ll, ll> seg[4 * maxn];

void propagate (int, int, int);

void change (int id, int L, int R, int l, int r, int val) {
	if (L == l and R == r) {
		lazy[id] += val;
		seg[id].F += val;
		return;
	}
	propagate (id, L, R);
	int mid = (L + R) >> 1;
	if (mid > l)
		change (2 * id + 0, L, mid, l, min (mid, r), val);
	if (mid < r)
		change (2 * id + 1, mid, R, max (l, mid), r, val);
	seg[id] = max (seg[2 * id + 0], seg[2 * id + 1]);
}

void propagate (int id, int L, int R) {
	if (lazy[id] == 0)
		return;
	int mid = (L + R) >> 1;
	change (2 * id + 0, L, mid, L, mid, lazy[id]);
	change (2 * id + 1, mid, R, mid, R, lazy[id]);
	lazy[id] = 0;
}

void modify (int id, int L, int R, int l, int r) {
	if (sec[id] <= 0)
		return;
	if (L + 1 == R) {
//		cout << L << " -> " << b[L] << endl;
		if (L + 1 < k) {
			change (1, 0, n, 0, L + 1, b[L]);
			change (1, 0, n, n - k + L + 1, n, b[L]);
		}
		else {
			change (1, 0, n, L - k + 1, L + 1, b[L]);
		}
		b[L] = 0;
		sec[id] = 0;
		return;
	}
	int mid = (L + R) >> 1;
	if (mid > l)
		modify (2 * id + 0, L, mid, l, min (mid, r));
	if (mid < r)
		modify (2 * id + 1, mid, R, max (l, mid), r);
	sec[id] = max (sec[2 * id + 0], sec[2 * id + 1]);
}

void build (int id, int L, int R) {
	if (L + 1 == R) {
		seg[id] = {0, L};
		sec[id] = b[L];
		return;
	}
	int mid = (L + R) >> 1;
	build (2 * id + 0, L, mid);
	build (2 * id + 1, mid, R);
	seg[id] = max (seg[2 * id + 0], seg[2 * id + 1]);
	sec[id] = max (sec[2 * id + 0], sec[2 * id + 1]);
}

ll solve (int N, int K, int c[], int d[]) {
    n = N, k = K;
    for (int i = 0; i < n; i++)
        a[i] = c[i];
    for (int i = 0; i < n; i++)
        b[i] = d[i];
	build (1, 0, n);
	for (int i = 0; i < n; i++)
		change (1, 0, n, i, i + 1, a[i]);
	for (int i = 0; i < n; i++) {
		if (i + 1 < k) {
			change (1, 0, n, 0, i + 1, -b[i]);
			change (1, 0, n, n - k + i + 1, n, -b[i]);
		}
		else {
			change (1, 0, n, i - k + 1, i + 1, -b[i]);
		}
	}
	ll ans = 0;
	while (true) { 
		auto it = seg[1];
		int idx = it.S;
		a[idx] = it.F;
//		cout << idx << " " << a[idx] << endl;
		if (a[idx] > 0) {
			ans += a[idx];
			if (idx + k <= n) {
				modify (1, 0, n, idx, idx + k);
			}
			else {
				modify (1, 0, n, idx, n);
				modify (1, 0, n, 0, (idx + k) - n);
			}
		
			change (1, 0, n, idx, idx + 1, -inf);
			a[idx] = 0;
		}
		else {
			break;
		}
	}
    return ans;
}

Compilation message (stderr)

homecoming.cpp: In function 'll solve(int, int, int*, int*)':
homecoming.cpp:87:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < n; i++)
     ^~~
homecoming.cpp:89:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  build (1, 0, n);
  ^~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38