oj.uz

Submission #202925

# Submission time Handle Problem Language Result Execution time Memory
202925 2020-02-18T17:16:25 Z arnold518 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 2508 ms 68748 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = (1<<20);
const int MAXQ = 2e6;

int N, Q;

struct SEG
{
	int tree[MAXN*2+10], A[MAXN+10], cnt[30];

	SEG()
	{
		memset(tree, 0, sizeof(tree));
		memset(A, 0, sizeof(A));
		memset(cnt, 0, sizeof(cnt));
	}

	void update2(int node, int tl, int tr, int dep, int pos, int val)
	{
		if(tl!=tr && !(tree[node]==0 || tree[node]==(tr-tl+1))) cnt[dep+1]+=val*2;
		if(tl==tr) return;
		int mid=tl+tr>>1;
		if(pos<=mid) update2(node*2, tl, mid, dep+1, pos, val);
		else update2(node*2+1, mid+1, tr, dep+1, pos, val);
	}

	void update(int node, int tl, int tr, int dep, int pos, int val)
	{
		tree[node]+=val;
		if(tl==tr) return;
		int mid=tl+tr>>1;
		if(pos<=mid) update(node*2, tl, mid, dep+1, pos, val);
		else update(node*2+1, mid+1, tr, dep+1, pos, val);
	}

	void update(int x)
	{
		if(A[x]==0)
		{
			A[x]=1;
			update2(1, 1, (1<<N), 0, x, -1);
			update(1, 1, (1<<N), 0, x, 1);
			update2(1, 1, (1<<N), 0, x, 1);
		}
		else
		{
			A[x]=0;
			update2(1, 1, (1<<N), 0, x, -1);
			update(1, 1, (1<<N), 0, x, -1);
			update2(1, 1, (1<<N), 0, x, 1);
		}
	}
}seg[2];

int main()
{
	int i, j;

	scanf("%d%d", &N, &Q);
	for(i=1; i<=Q; i++)
	{
		int t, x;
		scanf("%d%d", &t, &x);
		seg[t].update(x);

		ll ans=1;
		for(j=1; j<=N; j++) ans+=(ll)(1<<j)*(ll)(1<<j)-((ll)(1<<j)-seg[0].cnt[j])*((ll)(1<<j)-seg[1].cnt[j]);

		printf("%lld\n", ans);
	}
}

Compilation message

collecting.cpp: In member function 'void SEG::update2(int, int, int, int, int, int)':
collecting.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
collecting.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
collecting.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=tl+tr>>1;
           ~~^~~
collecting.cpp: In function 'int main()':
collecting.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
collecting.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &t, &x);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24952 KB Output is correct
2 Correct 18 ms 24952 KB Output is correct
3 Correct 23 ms 24952 KB Output is correct
4 Correct 23 ms 24956 KB Output is correct
5 Correct 18 ms 24952 KB Output is correct
6 Correct 21 ms 24952 KB Output is correct
7 Correct 18 ms 24952 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24952 KB Output is correct
2 Correct 19 ms 24952 KB Output is correct
3 Correct 23 ms 24952 KB Output is correct
4 Correct 20 ms 24952 KB Output is correct
5 Correct 20 ms 24952 KB Output is correct
6 Correct 23 ms 24952 KB Output is correct
7 Correct 19 ms 24952 KB Output is correct
8 Correct 22 ms 24956 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2508 ms 60480 KB Output is correct
2 Correct 2324 ms 52616 KB Output is correct
3 Correct 2148 ms 50484 KB Output is correct
4 Correct 2281 ms 52944 KB Output is correct
5 Correct 2238 ms 52444 KB Output is correct
6 Correct 2233 ms 51312 KB Output is correct
7 Correct 2342 ms 52592 KB Output is correct
8 Correct 2298 ms 52544 KB Output is correct
9 Correct 2089 ms 55104 KB Output is correct
10 Correct 2224 ms 51380 KB Output is correct
11 Correct 2252 ms 66420 KB Output is correct
12 Correct 2377 ms 68748 KB Output is correct
13 Correct 2249 ms 68304 KB Output is correct