oj.uz

Submission #202923

# Submission time Handle Problem Language Result Execution time Memory
202923 2020-02-18T17:08:19 Z arnold518 즐거운 사진 수집 (JOI13_collecting) C++14
30 / 100
 2477 ms 86820 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+=(ll)(1<<j)*(ll)(1<<j)-((ll)(1<<j)-seg[0].cnt[j])*((ll)(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
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2477 ms 69516 KB Output is correct
2 Correct 2422 ms 86432 KB Output is correct
3 Correct 2213 ms 83416 KB Output is correct
4 Correct 2473 ms 86820 KB Output is correct
5 Correct 2274 ms 86088 KB Output is correct
6 Correct 2311 ms 85120 KB Output is correct
7 Correct 2406 ms 86212 KB Output is correct
8 Correct 2412 ms 86404 KB Output is correct
9 Correct 2131 ms 82040 KB Output is correct
10 Correct 2246 ms 84648 KB Output is correct
11 Execution timed out 979 ms 60064 KB Time limit exceeded (wall clock)
12 Halted 0 ms 0 KB -