Submission #259292

#	Time	Username	Problem	Language	Result	Execution time	Memory
259292		pure_mem	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	2 ms	384 KiB

bridge

#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define MP make_pair
 
using namespace std;
 
const int N = 1e5 + 12;
const ll INF = 1e15;

int n, k;
vector< pair<int, int> > gr;

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
    cin >> k >> n;
    ll res = 0;
    for(int i = 1;i <= n;i++){
    	char x1, x2;
    	int y1, y2;
    	cin >> x1 >> y1 >> x2 >> y2;
    	if(y1 > y2)
    		swap(y1, y2);
    	if(x1 != x2){
    		gr.push_back(MP(y1, -1));
    		gr.push_back(MP(y2, 1));	
    		res += 1;
    	}
    	else{
    	    res += y2 - y1;
    	}
    }
    sort(gr.begin(), gr.end());
    int mxcnt = 0, curs = 0;
    for(pair<int, int> v: gr){
    	curs -= v.Y;
    	mxcnt = max(mxcnt, curs);
    }
    int my_edge = 0;
    for(pair<int, int> v: gr){
    	curs -= v.Y;
    	if(curs == mxcnt){
    		my_edge = v.X;
    	}
    }
    //cerr << my_edge << "\n";
    for(pair<int, int> v: gr){
    	res += abs(my_edge - v.X);
    }
    cout << res;
}

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