Submission #443999

#	Time	Username	Problem	Language	Result	Execution time	Memory
443999		moonrabbit2	Palembang Bridges (APIO15_bridge)	C++17	22 / 100	95 ms	6368 KiB

bridge

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 l2;
//typedef long long l2;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<db,db,db> tdb;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef tuple<int,int,int,int,int> ti5;
typedef tuple<ll,ll,ll,ll> tl4;
typedef tuple<db,db,db,db> td4;
typedef vector<vector<ll>> mat;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //shuffle(a+1,a+1+n,rng)
uniform_int_distribution<> gen(1,100); //gen(rng)

//https://codeforces.com/contest/1264/submission/66344993 + 몇 가지 기능 직접 추가
ll modinv(ll a,ll m){
	if(m==1) return 0;
	a%=m;
	if(a<0) a+=m;
	if(a==1) return 1;
	return m-modinv(m,a)*m/a;
}
template <int MOD_> struct modnum{
private:
	int v;
public:
	static const int MOD = MOD_;
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int () const { return v; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
	friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
	friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
	friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
	friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
	modnum operator ~ () const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}
 
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= (~o);
	}
	modnum operator-() const { return modnum(-v); }
	modnum& operator++() { return *this += 1; }
	modnum operator++(int){ modnum tmp=*this; ++*this; return tmp; }
	modnum& operator--() { return *this -= 1; }
	modnum operator--(int){ modnum tmp=*this; --*this; return tmp; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
	friend modnum pow(modnum a, ll p) {
		modnum ans = 1;
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend ostream& operator<<(std::ostream& os, const modnum& o)
	{
		os << o.v;
		return os;
	}
	friend istream& operator>>(std::istream& is, modnum& o)
	{
		is >> o.v;
		return is;
	}
	int get(){
		return v;
	}
};
const ll mod=1e9+7,inf=1e18;
using mi=modnum<mod>;
const int N=1e5+5,M=1e6+5;
int n,m,k,a[N],b[N],c[N];
ll res,ans,pfx[N],sfx[N],S;
priority_queue<int> S1;
priority_queue<int,vector<int>,greater<int>> S2;
void Insert(int x){
	int L=S1.top(),R=S2.top();
	if(L<=x&&x<=R){
		if(S1.size()<S2.size()){
			S1.push(x); S-=x;
		}
		else{
			S2.push(x); S+=x;
		}
	} else if(x<L){
		S1.push(x); S-=x;
		if(S1.size()>S2.size()+1){
			S2.push(S1.top()); S+=2*S1.top();
			S1.pop();
		}
	} else{
		S2.push(x); S+=x;
		if(S2.size()>S1.size()+1){
			S1.push(S2.top()); S-=2*S2.top();
			S2.pop();
		}
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>k>>m;
	for(int i=1;i<=m;i++){
		int A,B; char P,Q;
		cin>>P>>A>>Q>>B;
		if(P==Q){
			res+=abs(A-B); continue;
		}
		a[++n]=A; b[n]=B; c[n]=n;
	}
	sort(c+1,c+1+n,[&](int X,int Y){
		return a[X]+b[X]<a[Y]+b[Y];
	});
	for(int i=n;i>=1;i--){
		if(i==n){
			S1.push(min(a[c[i]],b[c[i]]));
			S2.push(max(a[c[i]],b[c[i]]));
			S=max(a[c[i]],b[c[i]])-min(a[c[i]],b[c[i]]);
		} else{
			Insert(a[c[i]]); Insert(b[c[i]]);
		}
		sfx[i]=S;
	}
	while(S1.size()) S1.pop();
	while(S2.size()) S2.pop();
	for(int i=1;i<n;i++){
		if(i==1){
			S1.push(min(a[c[i]],b[c[i]]));
			S2.push(max(a[c[i]],b[c[i]]));
			S=max(a[c[i]],b[c[i]])-min(a[c[i]],b[c[i]]);
		} else{
			Insert(a[c[i]]); Insert(b[c[i]]);
		}
		pfx[i]=S;
	}
	ans=inf;
	if(k==1) ans=sfx[1];
	else for(int i=0;i<n;i++) ans=min(ans,pfx[i]+sfx[i+1]);
	cout<<ans+n+res;
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37