Submission #34005

#	Time	Username	Problem	Language	Result	Execution time	Memory
34005		ngkan146	즐거운 사진 수집 (JOI13_collecting)	C++98	100 / 100	2373 ms	34784 KiB

collecting

#include <bits/stdc++.h>
using namespace std;
const int N = (1<<20) + 5;
int n,q,lgn;
int seg[2][4*N], sum[2][25];
void build(int id,int l,int r){
	if (l == r){
		seg[0][id] = seg[1][id] = 0;
		return;
	}
	build(2*id,l,(l+r)/2);
	build(2*id+1,(l+r)/2+1,r);
	seg[0][id] = seg[1][id] = 0;
}
void upd(int type,int id,int l,int r,int pos,int layer){
	if (r < pos || pos < l) return;
	if (l == r){
		seg[type][id] ^= 1;
		return;
	}
	upd(type, 2*id, l, (l+r)/2, pos, layer+1);
	upd(type, 2*id+1, (l+r)/2+1, r, pos, layer+1);
	sum[type][layer] -= (seg[type][id] != -1);
	
	if (seg[type][2*id] == -1 || seg[type][2*id+1] == -1) 
		seg[type][id] = -1;
	else if (seg[type][2*id] != seg[type][2*id+1])
		seg[type][id] = -1;
	else
		seg[type][id] = seg[type][2*id];
	sum[type][layer] += (seg[type][id] != -1);
	
}
void prep(){
	build(1,1,n);
	for(int i=0;i<=lgn;i++)	sum[0][i] = sum[1][i] = (1<<i);
}
int main(){
	scanf("%d %d",&n,&q);
	lgn = n;
	n = (1<<n);
	prep();
	while(q--){
		int type, pos;
		scanf("%d %d",&type,&pos);
		upd(type,1,1,n,pos,0);
		long long res = 0;
		long long used = 0;
		for(int layer = 0;layer <= lgn; layer++){
			
			res += 1ll * ((1ll<<2*layer) - used);
			used = 4ll * sum[0][layer] * sum[1][layer];
			//cout << sum[0][layer] << ' ' << sum[1][layer] << ' ' << res << endl;
		}
		printf("%lld\n",res);
	}
}

Compilation message (stderr)

collecting.cpp: In function 'int main()':
collecting.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
                      ^
collecting.cpp:45:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&type,&pos);
                            ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70