oj.uz

Submission #24909

# Submission time Handle Problem Language Result Execution time Memory
24909 2017-06-17T05:42:38 Z khsoo01 즐거운 사진 수집 (JOI13_collecting) C++11
100 / 100
 2669 ms 90756 KB 
#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

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.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2499 ms 90756 KB Output is correct
2 Correct 2523 ms 90756 KB Output is correct
3 Correct 2296 ms 90756 KB Output is correct
4 Correct 2533 ms 90756 KB Output is correct
5 Correct 2373 ms 90756 KB Output is correct
6 Correct 2519 ms 90756 KB Output is correct
7 Correct 2649 ms 90756 KB Output is correct
8 Correct 2669 ms 90756 KB Output is correct
9 Correct 2009 ms 90756 KB Output is correct
10 Correct 2103 ms 90756 KB Output is correct
11 Correct 2186 ms 90756 KB Output is correct
12 Correct 2306 ms 90756 KB Output is correct
13 Correct 2019 ms 90756 KB Output is correct