oj.uz

Submission #197779

# Submission time Handle Problem Language Result Execution time Memory
197779 2020-01-23T02:27:21 Z sean617 즐거운 사진 수집 (JOI13_collecting) C++
10 / 100
 5000 ms 1084 KB 
#include <iostream>
#include <cstdio>
#define N 8000000
using namespace std;

typedef long long ll;
ll n, m, k, s[25];
ll r[N], c[N];

bool chr(ll p, ll q) {
	ll i, re = 0, wa = (q - p + 1);
	p += k;
	q += k;
	while (p < q) {
		if (p % 2 == 1) re += r[p++];
		if (q % 2 == 0) re += r[q--];
		p /= 2;
		q /= 2;
	}
	if (p == q) re += r[p];
	if (re == 0 || re == wa) return 1;
	return 0;
}

bool chc(ll p, ll q) {
	ll i, re = 0, wa = (q - p + 1);
	p += k;
	q += k;
	while (p < q) {
		if (p % 2 == 1) re += c[p++];
		if (q % 2 == 0) re += c[q--];
		p /= 2;
		q /= 2;
	}
	if (p == q) re += c[p];
	if (re == 0 || re == wa) return 1;
	return 0;
}

ll f(ll p, ll q, ll w) {
	ll i, sz, re = 0;
	if (w == 0) return 1;
	sz = s[w];
	if (chr(p, p + sz - 1) && chc(q, q + sz - 1)) return 1;
	re += f(p, q, w - 1);
	re += f(p, q + sz / 2, w - 1);
	re += f(p + sz / 2, q, w - 1);
	re += f(p + sz / 2, q + sz / 2, w - 1);
	return re + 1;
}

int main()
{
	ll i, j, z, x;
	cin >> n >> m;
	s[0] = 1;
	for (i = 1; i <= 20; i++) s[i] = s[i - 1] * 2;
	for (k = 1; k < s[n]; k *= 2);
	while (m--) {
		scanf ("%lld %lld", &z, &x);
		x--;
		if (z == 0) {
			r[k + x] = 1 - r[k + x];
			for (j = (k + x) / 2; j >= 1; j /= 2) r[j] = r[j * 2] + r[j * 2 +1];
		}
		else {
			c[k + x] = 1 - c[k + x];
			for (j = (k + x) / 2; j >= 1; j /= 2) c[j] = c[j * 2] + c[j * 2 +1];
		}
		printf("%lld\n", f(0, 0, n));
	}
    return 0;
}

Compilation message

collecting.cpp: In function 'bool chr(ll, ll)':
collecting.cpp:11:5: warning: unused variable 'i' [-Wunused-variable]
  ll i, re = 0, wa = (q - p + 1);
     ^
collecting.cpp: In function 'bool chc(ll, ll)':
collecting.cpp:26:5: warning: unused variable 'i' [-Wunused-variable]
  ll i, re = 0, wa = (q - p + 1);
     ^
collecting.cpp: In function 'll f(ll, ll, ll)':
collecting.cpp:41:5: warning: unused variable 'i' [-Wunused-variable]
  ll i, sz, re = 0;
     ^
collecting.cpp: In function 'int main()':
collecting.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld %lld", &z, &x);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5043 ms 408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5062 ms 1084 KB Time limit exceeded
2 Halted 0 ms 0 KB -