oj.uz

Submission #202924

# Submission time Handle Problem Language Result Execution time Memory
202924 2020-02-18T17:14:20 Z arnold518 즐거운 사진 수집 (JOI13_collecting) C++14
30 / 100
 571 ms 51472 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
{
	vector<int> tree, A, cnt;

	SEG()
	{
		tree.resize(MAXN*4+10);
		A.resize(MAXN+10);
		cnt.resize(30);
	}

	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 30 ms 41336 KB Output is correct
2 Correct 29 ms 41336 KB Output is correct
3 Correct 30 ms 41336 KB Output is correct
4 Correct 28 ms 41336 KB Output is correct
5 Correct 28 ms 41336 KB Output is correct
6 Correct 29 ms 41336 KB Output is correct
7 Correct 30 ms 41336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 41464 KB Output is correct
2 Correct 30 ms 41336 KB Output is correct
3 Correct 31 ms 41336 KB Output is correct
4 Correct 31 ms 41340 KB Output is correct
5 Correct 30 ms 41464 KB Output is correct
6 Correct 31 ms 41464 KB Output is correct
7 Correct 30 ms 41340 KB Output is correct
8 Correct 29 ms 41336 KB Output is correct

Subtask #3
0 / 70.0

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