Submission #1279805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279805		mhn_neek	Arranging Tickets (JOI17_arranging_tickets)	C++20	0 / 100	3 ms	572 KiB

arranging_tickets

//In the name of God
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N=4e5+100;
const lli mod=1e9+7;//998244353;//1e9+9
const lli INF=1e18;
lli power(lli x,lli y){lli res = 1;x = x % mod;while(y>0){if( y & 1 ){res = (res * x) % mod;}y = y >> 1;x = (x * x)%mod;}return res;}
#define all(v) v.begin(),v.end()
#define debug(x) cerr << (#x) << " " << (x) << endl
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define FOR(x,n) for(int x = 0; x < n; x++)
#define FORS(x,n) for(int x = 1; x <= n; x++)
#define TEST int TQPWIEJR; cin>>TQPWIEJR;while(TQPWIEJR--)
#define endl "\n"
int n,m;
vp E;
lli pos[N],A[N],ps[N];
ve L[N];

lli solve(lli in){
	lli p = 1;
	pos[in] = 1;
	A[p++] = in;
	for(lli i = (in == n ? 1 : in+1); i != in; i = (i == n ? 1 : i+1)){
		A[p++] = i;
		pos[i] = p-1;
	}
	for(auto [a,b] : E){
		if(pos[a] > pos[b])swap(a,b);
		a = pos[a],b = pos[b];
		L[a].PB(b);
		ps[a] += 1;
		ps[b] -= 1;
	}
	FORS(i,n)ps[i] += ps[i-1];
	lli ans = 0;
	multiset<lli> S;
	multiset<pii> H;
	FORS(i,n-1){
		for(auto j : L[i])H.insert(MP(j,i));
		while(S.size() && *S.begin()<=i){S.erase(S.begin());}
		while(H.size() && (*H.begin()).fi<=i){H.erase(H.begin());}
		while((lli)S.size()*2 < ps[i]){
			if(H.empty())return INF;
			pii P = *H.rbegin();
			H.erase(H.find(P));
			S.insert(P.fi);
			ans ++;
		}

	}	
	FOR(i,n+1){
		L[i].clear();
		pos[i] = A[i] = ps[i] = 0;
	}
	return ans;
}

int main(){
    ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
	cin>>n>>m;
	FOR(i,m){
		lli a,b,c;
		cin>>a>>b>>c;
		E.PB(MP(a,b));
	}
	lli ans = INF;
	FORS(i,2){
		ans = min(ans,solve(i));
	}
	cout<<ans<<endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15