Submission #660000

#	Time	Username	Problem	Language	Result	Execution time	Memory
660000		highway_to_hell	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	92 ms	20120 KiB

bridge

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<long long , long long>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 2e5 + 5;
const long long mod = 1000000001;
const int sq = 740;
typedef long long ll;
ll l,r,mid;
ll n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
ll darage[maxm] , ss , mm;
queue<int> q;
vector<int> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm] , gos[maxm];
ll pedaret[maxm];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
void merge(ll r , ll q){
    if (get_par(r)!=get_par(q))l+=max(darage[r],darage[q])*1ll*sath[r]*1ll*sath[q];
    r = get_par(r) , q = get_par(q);
    if (r!=q){
        if (sath[r]<sath[q]) swap(r,q);
        pedaret[q] = r;
        sath[r] += sath[q];
    }
    return ;
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<ll> st;
ll rp[maxm];
ll dp[maxm];
pi W[maxm];
int rw[400][400];
int dage[305];
vector<int> vec;
map<ll,ll> mp;
void dfs(int u , int rang , int jad){
	darage[u] = rang;
	pedaret[rang]++;
	for (auto x : g[u]){
		if (x!=jad) dfs(x,1-rang,u);
	}
	return ;
}
priority_queue<int> lowq;
priority_queue<int, vector<int>, greater<int> > upq;
int h,w;
void prep(){
	memset(dage,0,sizeof dage);
}
void solve(int x){
	ll ans = 0;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			if(!dage[rw[i][j]]) ans++;
			dage[rw[i][j]]++;
		}
	}
	for (int i=1; i<=w; i++){
		for (int j=x; j<=x+h-1; j++){
			if (dage[rw[j][i]]==1) ans--;
			dage[rw[j][i]]--;
		}
	}
	//cout<<ans<<endl;
	vec.push_back(ans);
	for (int i=2; i<=m-w+1; i++){
		if (i!=1){
			for (int j=x; j<=x+h-1; j++){
				if (dage[rw[j][i-1]]==0) ans++;
				dage[rw[j][i-1]]++;
			}
		}
		for (int j=x; j<=x+h-1; j++){
			if (dage[rw[j][i+w-1]]==1) ans--;
			dage[rw[j][i+w-1]]--;
		}
		vec.push_back(ans);
	}
}
bool cmp(pi x, pi y){ return x.first+x.second<y.first+y.second; }
void appen(int x){
    mm = (lowq.size()?lowq.top():mod);
    if (x<=mm) lowq.push(x) , r+=x;
	else upq.push(x) , l+=x;	
    if (upq.size() + 1 < lowq.size()) {
		auto y = lowq.top();
		lowq.pop();
		upq.push(y);
		r-=y;
		l+=y;
	} 
	else if (lowq.size()<upq.size()) {
		auto y=upq.top();
		upq.pop();
		lowq.push(y);
		l-=y;
		r+=y;
	}
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >>m>>n;
	for (int i=1; i<=n; i++){
		char x,y;
		cin >>x>>l>>y>>r;
		if (y==x) mid+=abs(r-l);
		else{
			ss++;
			mid++;
			W[ss] = {l,r};
		}
	}
	if (m==1){
	    for(int i=1; i<=ss; i++){
	        darage[i]=W[i].first;
	        darage[i+ss]=W[i].second;
	    }
	    sort(darage+1,darage+1+2*ss);
	    mm = darage[ss];
	    for(int i=1; i<=2*ss; i++) mid+=abs(darage[i]-mm);
	    cout<<mid<<endl;
	}
	else{
		sort(W+1ll,W+1+ss,cmp);
		l = 0 , r = 0;
		for (int i=1; i<=ss; i++){
	        appen(W[i].first) , appen(W[i].second);
	        pedaret[i]=l-r;
	    }
	    while(!lowq.empty()) lowq.pop();
	    while (!upq.empty()) upq.pop();
	    l = 0 , r = 0; 
	    ll ans = pedaret[ss];
	    for(int i=ss; i>0; i--){
	        appen(W[i].first) , appen(W[i].second);
	        ans = min(ans,l-r+pedaret[i-1]);
	    }
	    cout<<mid+ans<<endl;
	}
}

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