Submission #202925

#	Time	Username	Problem	Language	Result	Execution time	Memory
202925		arnold518	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	2508 ms	68748 KiB

collecting

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70