oj.uz

답안 #787327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
787327 2023-07-19T05:25:45 Z 박영우(#10035) 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 3018 ms 44456 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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