oj.uz

Submission #102789

# Submission time Handle Problem Language Result Execution time Memory
102789 2019-03-27T14:09:48 Z njchung99 즐거운 사진 수집 (JOI13_collecting) C++14
30 / 100
 5000 ms 41580 KB 
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll seg[1 << 22];
ll seg1[1 << 22];
ll cc[1 << 20 + 1];
ll cc1[1 << 20 + 1];
ll n, m;
ll check[22];
ll update(ll pos, ll val, ll node, ll x, ll y)
{
	if (pos < x || y < pos)return seg[node];
	if (x == y)return seg[node] = val;
	ll mid = (x + y) / 2;
	return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
ll update1(ll pos, ll val, ll node, ll x, ll y)
{
	if (pos < x || y < pos)return seg1[node];
	if (x == y)return seg1[node] = val;
	ll mid = (x + y) / 2;
	return seg1[node] = update1(pos, val, node * 2, x, mid) + update1(pos, val, node * 2 + 1, mid + 1, y);
}
ll query(ll node, ll x, ll y,ll depth)
{
	ll ch = seg[node];
	ll mid = (x + y) / 2;
	if (ch == 0 || ch == (y - x + 1)) {
		return 0;
	}
	check[depth]++;
	return query(node * 2, x, mid, depth + 1) + query(node * 2+1, mid+1, y, depth + 1)+2*(1<<(depth+1));
}
ll query1(ll node, ll x, ll y,ll depth)
{
	ll ch = seg1[node];
	ll mid = (x + y) / 2;
	if (ch == 0 || ch == (y - x + 1)) {
		return 0;
	}
	ll gap = 2 * (1 << (depth + 1));
	return query1(node * 2, x, mid, depth + 1) + query1(node * 2 + 1, mid + 1, y, depth + 1) + gap-(gap/(1<<depth)*check[depth]);
}
int main()
{
	scanf("%lld %lld", &n, &m);
	for (ll i = 1; i <= m; i++)
	{
		memset(check, 0, sizeof(check));
		ll q, w;
		scanf("%lld %lld", &q, &w);
		if (q == 0) {
			cc[w] ^= 1;
			update(w, cc[w], 1, 1, (1 << n));
		}
		else
		{
			cc1[w] ^= 1;
			update1(w, cc1[w], 1, 1, (1 << n));
		}
		ll dap = query(1, 1, 1 << n, 0);
		dap += query1(1, 1, (1 << n), 0);
		printf("%lld\n", dap+1);
	}
}

Compilation message

collecting.cpp:8:15: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 ll cc[1 << 20 + 1];
            ~~~^~~
collecting.cpp:9:16: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 ll cc1[1 << 20 + 1];
             ~~~^~~
collecting.cpp: In function 'int main()':
collecting.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
collecting.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &q, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 512 KB Output is correct
2 Correct 28 ms 504 KB Output is correct
3 Correct 38 ms 384 KB Output is correct
4 Correct 48 ms 384 KB Output is correct
5 Correct 30 ms 384 KB Output is correct
6 Correct 50 ms 384 KB Output is correct
7 Correct 19 ms 384 KB Output is correct
8 Correct 13 ms 484 KB Output is correct

Subtask #3
0 / 70.0

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