Submission #259318

#	Time	Username	Problem	Language	Result	Execution time	Memory
259318		shayan_p	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	25 ms	3040 KiB

bridge

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, inf = 1e9 + 1;
const ll INF = 1e18;

ll sv[maxn];

int pt;
map<int, int> Ls, Rs;
set<int> All;
int CR, CL;
ll ANS;

void restart(){
    pt = -inf;
    Ls.clear(), Rs.clear(), All.clear();
    CR = CL = 0;
    ANS = 0;
}
ll add(int f, int s){
    if(All.empty()){
	pt = s;
	CR = 1;	
    }
    else{
	if(s <= pt)
	    CR++;
	if(pt < f)
	    CL++;
	if(pt < f)
	    ANS+= f - pt;
	if(s < pt)
	    ANS+= pt - s;
    }
    
    Ls[f]++, Rs[s]++;
    All.insert(f), All.insert(s);

    while(CR < CL){
	int nw = *All.upper_bound(pt);
	ANS+= 1ll * (nw - pt) * (CR - CL);
	if(Rs.count(nw))
	    CR+= Rs[nw];
	if(Ls.count(nw))
	    CL-= Ls[nw];
	pt = nw;
    }
    return ANS * 2;
}

int arr[maxn], C;
    
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int k, n;
    cin >> k >> n;
    ll sig = 0;
    vector<pii> inp;
    for(int i = 0; i < n; i++){
	char a, b;
	int l, r;
	cin >> a >> l >> b >> r;
	if(r < l)
	    swap(l, r);
	sig+= r-l;
	if(a != b){
	    sig++;
	    inp.PB({l, r});
	}
    }
    sort(inp.begin(), inp.end(), [](pii a, pii b){ return a.F + a.S < b.F + b.S; } );
    n = sz(inp);

    if(n == 0)
	return cout << sig << endl, 0;
    
    ll ans = INF;
    for(pii p : inp)
	arr[C++] = p.F, arr[C++] = p.S;
    sort(arr, arr + C);
    C = unique(arr, arr + C) - arr;
    
    for(int i = 0; i < C; i++){
	for(int j = 0; j < n; j++){
	    if(arr[i] < inp[j].F)
		sv[i]+= inp[j].F - arr[i];
	    if(inp[j].S < arr[i])
		sv[i]+= arr[i] - inp[j].S;
	}
	ans = min(ans, sig + 2 * sv[i]);
    }
    bool is = 0;
    for(int i = 0; i < C-1; i++){
	if(is == 0 && sv[i] < sv[i+1])
	    is = 1;
	if(is && sv[i] > sv[i+1])
	    assert(0);
    }
    return cout << ans << endl, 0;

    
    /*    restart();
    for(int i = 0; i < n; i++){
	sv[i + 1] = add(inp[i].F, inp[i].S);
    }
    restart();    
    ll ans = INF;
    for(int i = n-1; i >= 0; i--){
	ans = min(ans, sig + sv[i] + add(-inp[i].S, -inp[i].F));
    }
    if(k == 1)
	ans = sig + sv[n];
	return cout << ans << endl, 0;*/
    
}

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