Submission #787327

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
787327	2023-07-19T05:25:45 Z	박영우(#10035)	즐거운 사진 수집 (JOI13_collecting)	C++17	100 / 100	3018 ms	44456 KB

collecting

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 22
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 998244353
struct fenwick {
	int N;
	vector<int> tree;
	fenwick(int N = 0) :N(N) { tree.resize(N + 1); }
	void upd(int i, int x) { i++; while (i <= N) { tree[i] += x, i += i & -i; } }
	int get(int i) { i++; int sum = 0; while (i) { sum += tree[i], i -= i & -i; } return sum; }
	int get(int i, int j) { return get(j) - get(i - 1); }
};
int chk[2][1 << MAX];
int cnt[2][MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	int i;
	ll sum = 1;
	for (i = 1; i <= N; i++) sum += 1ll << (i << 1);
	fenwick fen[2];
	fen[0] = fen[1] = fenwick(1 << N);
	for (i = 0; i < N; i++) cnt[0][i] = cnt[1][i] = 1 << i;
	while (Q--) {
		int t, x;
		int l, r;
		cin >> t >> x;
		x--;
		l = r = x;
		for (i = 0; i <= N; i++) {
			l >>= i;
			l <<= i;
			r = l | ((1 << i) - 1);
			int res = fen[t].get(l, r);
			if (!res || res == (1 << i)) cnt[t][N - i]--;
		}
		if (chk[t][x]) fen[t].upd(x, -1);
		else fen[t].upd(x, 1);
		chk[t][x] ^= 1;
		l = r = x;
		for (i = 0; i <= N; i++) {
			l >>= i;
			l <<= i;
			r = l | ((1 << i) - 1);
			int res = fen[t].get(l, r);
			if (!res || res == (1 << i)) cnt[t][N - i]++;
		}
		ll ans = 0;
		for (i = 0; i < N; i++) ans += 1ll * cnt[0][i] * cnt[1][i];
		cout << sum - 4 * ans << Ln;
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct

Subtask #3

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3018 ms	44064 KB	Output is correct
2	Correct	2907 ms	44056 KB	Output is correct
3	Correct	2508 ms	33848 KB	Output is correct
4	Correct	2844 ms	44456 KB	Output is correct
5	Correct	2818 ms	43820 KB	Output is correct
6	Correct	2779 ms	42764 KB	Output is correct
7	Correct	2976 ms	44140 KB	Output is correct
8	Correct	2876 ms	44168 KB	Output is correct
9	Correct	2493 ms	33064 KB	Output is correct
10	Correct	2651 ms	34544 KB	Output is correct
11	Correct	2716 ms	43272 KB	Output is correct
12	Correct	2767 ms	42788 KB	Output is correct
13	Correct	2584 ms	34560 KB	Output is correct