Submission #1284537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284537		kerem	즐거운 사진 수집 (JOI13_collecting)	C++20	100 / 100	842 ms	60948 KiB

collecting

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 2000
#define inf (int)1e15
typedef pair<int,int> pii;

struct Calc{
	int n;
	vector<int> cnt;
	vector<int> st;
	Calc(int nn){
		n=nn;
		cnt.assign(n+1,0);
		st.assign((1<<(n+1)),-1);
		st[1]=0;cnt[n]=1;
	}
	void add(int x,int node=1,int k=1){
		if(node==x+(1<<n)){
			st[node]^=1;
			return;
		}
		if(st[node]!=2){
			cnt[n-k+1]--;
			cnt[n-k]+=2;
			st[node<<1]=st[node];
			st[node<<1|1]=st[node];
			st[node]=2;
		}
		if(x&(1<<(n-k))) add(x,node<<1|1,k+1);
		else add(x,node<<1,k+1);
	}
	void remove(int x){
		int node=x+=(1<<n),k=0;
		st[node]^=1;
		while(st[node]==st[node^1]){
			cnt[k+1]++;
			cnt[k]-=2;
			st[node>>1]=st[node];
			st[node]=st[node^1]=-1;
			node>>=1;k++;
		}
	}
};
void solve(){
	int n,q;
	cin >> n >> q;
	vector<Calc> a(2,Calc(n));
	while(q--){
		int t,x;
		cin >> t >> x;
		x--;
		if(a[t].st[x+(1<<n)]==-1)
			a[t].add(x);
		else a[t].remove(x); 
		int sum0=0,sum1=0;
		vector<int> cnt(n+1,0);
		for(int i=n;i>=0;i--){
			sum0+=a[0].cnt[i];
			sum1+=a[1].cnt[i];
			cnt[i]+=sum0*sum1;
			if(i) cnt[i-1]-=4*sum0*sum1;
			sum0*=2;sum1*=2;
		}
		int ans=0,sum=0;
		for(int i=0;i<=n;i++){
			sum+=cnt[i];sum/=4;
			ans+=cnt[i]+sum;
		}
		cout << ans << "\n";
	}
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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