oj.uz

Submission #102796

# Submission time Handle Problem Language Result Execution time Memory
102796 2019-03-27T14:26:16 Z njchung99 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 3350 ms 94280 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 check1[22];
ll dap;
ll update(ll pos, ll val, ll node, ll x, ll y,ll depth)
{
	if (pos < x || y < pos)return seg[node];
	if (x == y)return seg[node] = val;
	ll mid = (x + y) / 2;
	ll gap = 2 * (1 << (depth + 1));
	if (seg[node] == 0 || seg[node] == y - x + 1) {
		check[depth]++;
		dap += (gap - gap / (1 << depth)*check1[depth]);
	}
	seg[node] = update(pos, val, node * 2, x, mid,depth+1) + update(pos, val, node * 2 + 1, mid + 1, y,depth+1);
	if (seg[node] == 0 || seg[node] == y - x + 1)
	{
		check[depth]--;
		dap -= (gap - gap / (1 << depth)*check1[depth]);
	}
	return seg[node];
}
ll update1(ll pos, ll val, ll node, ll x, ll y,ll depth)
{
	if (pos < x || y < pos)return seg1[node];
	if (x == y)return seg1[node] = val;
	ll mid = (x + y) / 2;
	ll gap = 2 * (1 << (depth + 1));
	if (seg1[node] == 0 || seg1[node] == y - x + 1) {
		check1[depth]++;
		dap += (gap - gap / (1 << depth)*check[depth]);
	}
	seg1[node] = update1(pos, val, node * 2, x, mid, depth + 1) + update1(pos, val, node * 2 + 1, mid + 1, y, depth + 1);
	if (seg1[node] == 0 || seg1[node] == y - x + 1)
	{
		check1[depth]--;
		dap -= (gap - gap / (1 << depth)*check[depth]);
	}
	return seg1[node];
}
int main()
{
	scanf("%lld %lld", &n, &m);
	for (ll i = 1; i <= m; i++)
	{
		ll q, w;
		scanf("%lld %lld", &q, &w);
		if (q == 0) {
			cc[w] ^= 1;
			update(w, cc[w], 1, 1, (1 << n),0);
		}
		else
		{
			cc1[w] ^= 1;
			update1(w, cc1[w], 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:52: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:56: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 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3350 ms 93572 KB Output is correct
2 Correct 3259 ms 93940 KB Output is correct
3 Correct 2685 ms 66508 KB Output is correct
4 Correct 2523 ms 94280 KB Output is correct
5 Correct 2816 ms 93688 KB Output is correct
6 Correct 2833 ms 92776 KB Output is correct
7 Correct 2983 ms 93940 KB Output is correct
8 Correct 3012 ms 94056 KB Output is correct
9 Correct 2385 ms 65168 KB Output is correct
10 Correct 2825 ms 67712 KB Output is correct
11 Correct 2778 ms 92608 KB Output is correct
12 Correct 2701 ms 92620 KB Output is correct
13 Correct 2474 ms 67700 KB Output is correct