oj.uz

Submission #202921

# Submission time Handle Problem Language Result Execution time Memory
202921 2020-02-18T17:04:20 Z arnold518 즐거운 사진 수집 (JOI13_collecting) C++14
0 / 100
 585 ms 50596 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*4+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+=(1<<j)*(1<<j)-((1<<j)-seg[0].cnt[j])*((1<<j)-seg[1].cnt[j]);

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

		//for(j=1; j<=N; j++) printf("%d ", seg[0].cnt[j]); printf("\n");
		//for(j=1; j<=N; j++) printf("%d ", seg[1].cnt[j]); printf("\n");
		//printf("\n");
	}
}

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 41336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 41464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 585 ms 50596 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -