Submission #24909

#	Time	Username	Problem	Language	Result	Execution time	Memory
24909		khsoo01	즐거운 사진 수집 (JOI13_collecting)	C++11	100 / 100	2669 ms	90756 KiB

collecting

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, q, cnt[2][25], chk[2][1234567], ans;

struct segtree {
	ll val[4444444];
	ll unif (ll S, ll E, ll P) {
		return (val[P] == (E-S+1) || val[P] == 0);
	}
	void init (ll T, ll D, ll S, ll E, ll P) {
		if(D == n) return;
		cnt[T][D] += unif(S, E, P);
		ans -= unif(S, E, P) * cnt[T^1][D] * 4;
		ll mid = (S+E)/2;
		init(T, D+1, S, mid, 2*P);
		init(T, D+1, mid+1, E, 2*P+1);
	}
	void update (ll T, ll D, ll S, ll E, ll P, ll X, ll V) {
		if(D == n) {val[P] += V; return;}
		cnt[T][D] -= unif(S, E, P);
		ans += unif(S, E, P) * cnt[T^1][D] * 4;
		val[P] += V;
		cnt[T][D] += unif(S, E, P);
		ans -= unif(S, E, P) * cnt[T^1][D] * 4;
		ll mid = (S+E)/2;
		if(X <= mid) update(T, D+1, S, mid, 2*P, X, V);
		else update(T, D+1, mid+1, E, 2*P+1, X, V);
	}
} seg[2];

int main()
{
	scanf("%lld%lld",&n,&q);
	ans = (1ll << (2*n)) + ((1ll << (2*n)) - 1) / 3;
	seg[0].init(0, 0, 1, (1<<n), 1);
	seg[1].init(1, 0, 1, (1<<n), 1);
	while(q--) {
		ll A, B, V;
		scanf("%lld%lld",&A,&B);
		V = (chk[A][B] ^ 1) - chk[A][B];
		chk[A][B] ^= 1;
		seg[A].update(A, 0, 1, (1<<n), 1, B, V);
		printf("%lld\n",ans);
	}
}

Compilation message (stderr)

collecting.cpp: In function 'int main()':
collecting.cpp:34:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&q);
                         ^
collecting.cpp:40:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B);
                          ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70