Submission #1269448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269448		MateiKing80	JOI tour (JOI24_joitour)	C++20	16 / 100	208 ms	43468 KiB

joitour

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int N = 2e5 + 5;

struct node {
	int z, u, d, zu, ud, zud, du, uz, duz;
};

node join (node a, node b) {
	node c;
	c.z = a.z + b.z;
	c.u = a.u + b.u;
	c.d = a.d + b.d;
	c.zu = a.zu + b.zu + a.z * b.u;
	c.ud = a.ud + b.ud + a.u * b.d;
	c.zud = a.zud + a.zu * b.d + a.z * b.ud + b.zud;
	c.du = a.du + b.du + a.d * b.u;
	c.uz = a.uz + b.uz + a.u * b.z;
	c.duz = a.duz + a.du * b.z + a.d * b.uz + b.duz;
	return c;
}

node aint[4 * N];
int tip[N], n;

void build(int pos, int st, int dr) {
	if (st == dr) {
		aint[pos] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
		if (tip[st] == 0)
			aint[pos].z = 1;
		else if (tip[st] == 1)
			aint[pos].u = 1;
		else
			aint[pos].d = 1;
		return;
	}
	int mid = (st + dr) / 2;
	build (2 * pos, st, mid);
	build (2 * pos + 1, mid + 1, dr);
	aint[pos] = join(aint[2 * pos], aint[2 * pos + 1]);
}

void update(int pos, int st, int dr, int l, int v) {
	if (st == dr) {
		aint[pos] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
		if (v == 0)
			aint[pos].z = 1;
		else if (v == 1)
			aint[pos].u = 1;
		else
			aint[pos].d = 1;
		return;
	}
	int mid = (st + dr) / 2;
	if (l <= mid)
		update(2 * pos, st, mid, l, v);
	else
		update(2 * pos + 1, mid + 1, dr, l, v);
	aint[pos] = join(aint[2 * pos], aint[2 * pos + 1]);
}

void init(signed _N, vector<signed> F, vector<signed> U, vector<signed> V, signed Q) {
	n = _N;
	for (int i = 0; i < n; i ++)
		tip[i] = F[i];
	build(1, 0, n - 1);
}

void change(signed x, signed y) {
	update(1, 0, n - 1, x, y);
}

int num_tours() {
  return aint[1].zud + aint[1].duz;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 16 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 34
• Subtask 7: 0 / 14