Submission #659709

#	Time	Username	Problem	Language	Result	Execution time	Memory
659709		ymm	Inside information (BOI21_servers)	C++17	5 / 100	3572 ms	73288 KiB

servers

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 1<<17;
const int S = 512;

int cnt[N];
unsigned char cnt_buf[S]; int buf_sum = 0;
unsigned char bs[N][S];

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void merge(int i, int j)
{
	++buf_sum;
	Loop (k,0,S) {
		cnt_buf[k] -= bs[i][k] ^ bs[j][k];
		auto tmp = bs[i][k] ^ bs[j][k];
		bs[i][k] = tmp;
		bs[j][k] = tmp;
	}
}

void buf_flush()
{
	buf_sum = 0;
	Loop (i,0,S) {
		cnt[i] += cnt_buf[i];
		cnt_buf[i] = 0;
	}
}

void init(int off)
{
	buf_sum = 0;
	Loop (i,0,S) {
		cnt[i] = 0;
		cnt_buf[i] = 0;
	}
	Loop (i,0,N) {
		Loop (j,0,S)
			bs[i][j] = 0;
	}
	Loop (i,0,S) {
		bs[i+off][i] = -1;
		cnt[i]++;
	}
}

int qans[N*2];

struct {
	char type;
	int a, b;
} qr[N*2];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	q = n+q-1;
	Loop (i,0,q) {
		cin >> qr[i].type;
		switch (qr[i].type) {
		case 'S':
		case 'Q':
			cin >> qr[i].a >> qr[i].b;
			break;
		case 'C':
			cin >> qr[i].a;
			break;
		}
		--qr[i].a; --qr[i].b;
	}
	for (int off = 0; off < n; off += S) {
		init(off);
		Loop (i,0,q) {
			int a = qr[i].a;
			int b = qr[i].b;
			switch (qr[i].type) {
			case 'S':
				merge(a, b);
				break;
			case 'Q':
				if (off <= b && b < off + S)
					qans[i] = -bs[a][b-off];
				break;
			case 'C':
				if (off <= a && a < off + S)
					qans[i] = cnt[a-off]
							+ cnt_buf[a-off];
				break;
			}
			if (buf_sum == 255)
				buf_flush();
		}
	}
	Loop (i,0,q) {
		switch (qr[i].type) {
		case 'Q': cout << (qans[i]? "yes": "no") << '\n'; break;
		case 'C': cout << qans[i] << '\n'; break;
		}
	}
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5