Submission #1264495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264495		rainboy	Triple Peaks (IOI25_triples)	C++20	70 / 100	89 ms	31304 KiB

triples

/* discussed with lunchbox */
#include "triples.h"
#include <cstdlib>
#include <iostream>

using namespace std;

typedef vector<int> vi;

const int N = 200000;

int *ej[N * 3], eo[N * 3];

void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

char used[N * 3];

long long count_triangles(vi aa, int n) {
	for (int i = 0; i < n * 3; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (int i = 0; i < n; i++) {
		int l = n + i - aa[i], r = n + i + aa[i];
		append(l, r), append(r, l);
	}
	long long ans = 0;
	for (int i = 0; i < n * 3; i++) {
		for (int oi = eo[i]; oi--; ) {
			int j = ej[i][oi];
			used[j] = 1;
		}
		for (int oi = eo[i]; oi--; ) {
			int j = ej[i][oi];
			if (eo[i] > eo[j] || eo[i] == eo[j] && i < j)
				for (int oj = eo[j]; oj--; ) {
					int k = ej[j][oj];
					if (used[k])
						ans++;
				}
		}
		for (int oi = eo[i]; oi--; ) {
			int j = ej[i][oi];
			used[j] = 0;
		}
	}
	for (int i = 0; i < n * 3; i++)
		free(ej[i]);
	return ans / 3;
}

long long count_triples(vi aa) {
	int n = aa.size();
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		int j, k = i + aa[i];
		if (k < n && aa[k] < aa[i]) {
			j = k - aa[k];
			if (j > i && aa[j] == j - i)
				ans++;
			if (aa[k] * 2 != aa[i]) {
				j = i + aa[k];
				if (j < k && aa[j] == k - j)
					ans++;
			}
		}
	}
	for (int k = 0; k < n; k++) {
		int i = k - aa[k], j;
		if (i >= 0 && aa[i] < aa[k]) {
			j = i + aa[i];
			if (j < k && aa[j] == k - j)
				ans++;
			if (aa[i] * 2 != aa[k]) {
				j = k - aa[i];
				if (j > i && aa[j] == j - i)
					ans++;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		int j = i + aa[i];
		if (j < n && aa[j] > aa[i] && aa[j] != aa[i] * 2) {
			int k = i + aa[j];
			if (k < n && aa[k] == k - j)
				ans++;
		}
	}
	ans += count_triangles(aa, n);
	return ans;
}

vi construct_range(int M, int K) {
	return {1, 1, 1};
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 19
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5