mxqz ABC D
  • 板块学术版
  • 楼主Esawkm
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/10/7 21:41
  • 上次更新2023/11/2 14:59:15
查看原帖
mxqz ABC D
642481
Esawkm楼主2023/10/7 21:41

RT,TLE*11 ,感觉复杂度 O(n log a_i log a_i) 但是TLE

#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,jc[35];
long long ans;
struct qwqwq{
	int x,y;
}a[100005];
map<long long,int>mp;
map<long long,bool>vis,viss;
int cmp(qwqwq x,qwqwq y){
	return x.x<y.x;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	jc[0]=1;
	for(int i(1);i<=31;i++)
	jc[i]=jc[i-1]*2;
	cin>>n;
	for(int i(1);i<=n;i++)
	cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	for(int i(1);i<=n;i++)
	mp[a[i].x]=a[i].y;
	for(int i(1);i<=n;i++){
		for(int j(1);j<=30;j++)
		if(!viss[a[i].x*jc[j-1]])
		viss[a[i].x*jc[j-1]]=1,mp[a[i].x*jc[j]]+=mp[a[i].x*jc[j-1]]/2,mp[a[i].x*jc[j-1]]%=2;
	}
	/*for(int i(1);i<=15;i++)
	cout<<mp[i]<<' ';*/
	for(int i(1);i<=n;i++)
	for(int j(0);j<=30;j++)
	if(!vis[a[i].x*jc[j]])
	ans+=mp[a[i].x*jc[j]],vis[a[i].x*jc[j]]=1;
	cout<<ans;
	return 0;
}
2023/10/7 21:41
加载中...