双指针做法后面15个点全WA,求调
查看原帖
双指针做法后面15个点全WA,求调
422684
M1saka16I72楼主2024/2/28 23:22
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define mp_ make_pair
#define pb_ push_back
#define pob_ pop_back
#define fst first
#define snd second
#define debug cout<<"********\n";
#define reset(x,y) memset(x,y,sizeof(x))
#define fi(x) freopen(x,"r",stdin)
#define fo(x) freopen(x,"w",stdout)
#define iosf ios::sync_with_stdio(0);cin.tie(0);
#define prec(x) cout<<setprecision(x);
#define prec0(x) cout<<fixed<<setprecision(x);
#define s(x,y) x[y-1]
#define Misaka16172 sb

using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

using namespace std;

template <class T>
inline void read(T &x){
	x = 0;T w = 1;
	char c = 0;
	while(c<'0' || c>'9'){
		if(c=='-')	w = -1;
		c = getchar();
	}
	while(c>='0' && c<='9'){
		x = ((x<<3)+(x<<1))+c-'0';
		c = getchar();
	}
	x = x*w;
}

constexpr int N = 2e7+5;

ll s[N];

unordered_map<ll,int> vis;
unordered_map<ll,ll> cnt;

void solve(){
	// fi("abc323_d.in");
	int n;read(n);
	int x = 0;ll ns;
	for(int i=1;i<=n;i++){
		read(ns);
		if(!vis[ns]){
			x++;
			vis[ns] = x;
			s[x] = ns;
		}
		ll c;read(c);
		cnt[ns]+=c;
	}
	sort(s+1,s+1+n);
	for(int i=1;i<=n;i++){
		vis[s[i]] = i;
	}
	int l = 1,r = n;
	ll ans = 0;
	while(l<=r){
		int now = r+1;
		for(int i=l;i<now;i++){
			// cout<<i<<" "<<s[i]<<" "<<cnt[s[i]]<<" ";
			if(cnt[s[i]]>1){
				if(!vis[s[i]<<1ll]){
					r++;
					s[r] = (s[i]<<1ll);
					vis[s[r]] = r;
				}
				cnt[s[i]<<1ll]+=(cnt[s[i]]>>1ll);
				cnt[s[i]]&=1ll;
			}
			// cout<<cnt[s[i]]<<"\n";
			ans+=cnt[s[i]];
		}
		l = now;
	}
	cout<<ans;
}

int main(){
	int t = 1;
//	read(t);
	for(int tt=1;tt<=t;tt++){
		solve();
	}
}
2024/2/28 23:22
加载中...