Submission #1249543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249543		Edu175	Souvenirs (IOI25_souvenirs)	C++20	100 / 100	13 ms	420 KiB

souvenirs

#include "souvenirs.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((ll)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto i:v)cout<<i<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vv;

vv a;
struct conju{
	ll sum=0,l=-1;
	vector<int> ind;
	conju(vector<int> v, ll sum):sum(sum),ind(v){l=ind[0];}
	bool operator<(const conju& rhs) const {
		return l<rhs.l;
	}
	ll get() const {
		ll k=SZ(ind);
		return (sum+k-1)/k - 1;
	}
	ll back(){return ind.back();}
	void pop(){sum-=a[ind.back()],ind.pop_back();}
};

vv hist;
conju llama(ll s){
	auto [v,r]=transaction(s);
	for(auto i:v)hist[i]++;
	return conju(v,s-r);
}

priority_queue<conju> mata(priority_queue<conju> _pq, ll p){
	priority_queue<conju> pq;
	while(SZ(_pq)){
		auto c=_pq.top(); _pq.pop();
		if(c.back()==p)c.pop();
		if(SZ(c.ind))pq.push(c);
	}
	return pq;
}

void buy_souvenirs(int N, long long P0) {
	ll n=N;
	hist.resize(n);
	priority_queue<conju> pq;
	ll R=n-1;
	a=vv(n,-1);
	
	auto cut=[&](conju &c){
		while(c.back()>R)c.pop();
	};
	
	pq.push(llama(P0-1));
	while(R>=1){
		assert(SZ(pq));
		auto c=pq.top();
		if(c.l==R){
			a[R]=c.sum;
			pq=mata(pq,R);
			R--;
		}
		else {
			ll x=c.get();
			auto ci=llama(x);
			assert(c.l<ci.l&&ci.l<=R);
			cut(ci);
			pq.push(ci);
		}
	}
	
	fore(i,0,n){
		fore(_,0,i-hist[i])llama(a[i]);
	}
	
	return;
}

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 28 / 28
• Subtask 6: 33 / 33