oj.uz

답안 #24909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

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

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

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