#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
vector <long long> vmax[2*DIMN] , vmin[2*DIMN];
set <long long> s;
pair <long long,long long> nv[DIMN];
long long p[2*DIMN] , sol_sl[DIMN] , sol_sr[DIMN];
int cmp (pair <long long,long long> a , pair <long long,long long> b){
return a.first + a.second < b.first + b.second; /// sort dupa media aritmetica
}
long long findd (long long x , long long tot){
long long st , dr , mid;
st = 0;
dr = tot - 1;
while (st <= dr){
mid = (st + dr)/2;
if (p[mid] == x)
return mid;
else if (p[mid] < x)
st = mid + 1;
else dr = mid - 1;
}
return -1;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
long long k , n , elem , tot = 0 , tot2 = 0, i ,p1 , p2 , left , right , poz , j;
char c1 , c2;
long long sol , base , sl , sr , sum , summ;
fscanf (fin,"%lld%lld\n",&k,&n);
base = 0;
elem = 0;
for (i=1;i<=n;i++){
c1 = fgetc(fin);
fscanf (fin,"%lld ",&p1);
c2 = fgetc(fin);
fscanf (fin,"%lld\n",&p2);
if (c1 == c2){
base = base + max ( p2 - p1 , p1 - p2 );
}
else{
base = base + 1 + max ( p2 - p1 , p1 - p2 );
nv[++elem] = make_pair(min(p1,p2) , max(p1,p2));
p[tot++] = p1;
p[tot++] = p2;
}
}
sort ( p , p + tot);
tot2 = 0;
for (i=0;i<tot;i++){
if (i == 0 || p[i] != p[i-1])
p[tot2++] = p[i];
}
tot = tot2;
for (i=1;i<=elem;i++){
nv[i].first = findd (nv[i].first , tot);
nv[i].second = findd (nv[i].second , tot);
p1 = nv[i].first;
p2 = nv[i].second;
s.insert(p1);
s.insert(p2);
vmax[max(p1 ,p2)].push_back(min(p1 , p2));
vmin[min(p1 ,p2)].push_back(max(p1 , p2));
}
n = elem;
if (k == 1){ /// asta e ok
left = 0;
right = n - vmin[*(s.begin())].size();
sl = 0;
sr = 0;
for (i=1;i<=n;i++){
if (nv[i].first != *(s.begin()))
sr = sr + 2 * ( p[nv[i].first] - p[(*(s.begin()))] );
}
sol = 2000000000000000;
for (set <long long> :: iterator it = s.begin() ; it != s.end() ;){
poz = (*it);
// printf ("%lld ",poz);
sol = min(sol , sl + sr);
/// acum e timpul sa modific left ul si right ul
left = left + vmax[poz].size();
right = right - vmin[poz+1].size();
it++;
if (it == s.end())
break;
sl += 2 * (p[(*it)] - p[poz]) * left;
sr -= 2 * (p[(*it)] - p[poz]) * ( right + vmin[poz+1].size() );
}
if (sol == 2000000000000000)
sol = 0;
fprintf (fout,"%lld" , sol + base);
}
else { /// aici k = 2
/// construiesti pentru prefixe
/// cand faci media primelor i , faci media dintre sumele intre inc si sf
/// media aritmetica inc , inc+1 ... sf = media aritmetica inc sf
sort (nv + 1 , nv + elem + 1 , cmp); /// sort dupa media aritmetica
sum = 0;
for (i=1;i<=elem;i++){ /// pt prefixul 1..i de pozitii , daca ai pune pod?
sum = sum + nv[i].first + nv[i].second;
poz = sum / (2 * i); /// media
/// pt podurile 1 ... i cel mai bn e sa pui un pod aici
/// calcul
summ = 0;
for (j=1;j<=i;j++){
if (nv[i].first <= poz && poz <= nv[i].second)
continue;
else if (nv[i].first < poz && nv[i].second < poz)
summ = summ + 2 * (poz - nv[i].second);
else summ = summ + 2 * (nv[i].first - poz);
}
sol_sl[i] = summ;
poz = poz + 1; /// inca o varianta de medie pt ca nu se imparte exact?
/// calcul
summ = 0;
for (j=1;j<=i;j++){
if (nv[i].first <= poz && poz <= nv[i].second)
continue;
else if (nv[i].first < poz && nv[i].second < poz)
summ = summ + 2 * (poz - nv[i].second);
else summ = summ + 2 * (nv[i].first - poz);
}
sol_sl[i] = min(sol_sl[i] , summ);
}
sum = 0;
for (i=elem;i;i--){ /// pt prefixul 1..i de pozitii , daca ai pune pod?
sum = sum + nv[i].first + nv[i].second;
poz = sum / (2 * (elem - i + 1)); /// media
/// pt podurile 1 ... i cel mai bn e sa pui un pod aici
/// calcul
summ = 0;
for (j=n;j>i;j--){
if (nv[i].first <= poz && poz <= nv[i].second)
continue;
else if (nv[i].first < poz && nv[i].second < poz)
summ = summ + 2 * (poz - nv[i].second);
else summ = summ + 2 * (nv[i].first - poz);
}
sol_sr[i] = summ;
poz = poz + 1; /// inca o varianta de medie pt ca nu se imparte exact?
/// calcul
summ = 0;
for (j=n;j>i;j--){
if (nv[i].first <= poz && poz <= nv[i].second)
continue;
else if (nv[i].first < poz && nv[i].second < poz)
summ = summ + 2 * (poz - nv[i].second);
else summ = summ + 2 * (nv[i].first - poz);
}
sol_sr[i] = min(sol_sr[i] , summ);
}
/// conatruiesti pentru sufixe
sol = 2000000000000;
sol = min (sol_sl[elem] , sol_sr[1]);
for (i = 1 ; i < elem ; i++){
sol = min(sol , sol_sl[poz] + sol_sr[poz + 1]);
}
if (sol == 2000000000000)
sol = 0;
fprintf (fout,"%lld" , sol + base);
}
return 0;
}
Compilation message
bridge.cpp: In function 'int main()':
bridge.cpp:37:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld%lld\n",&k,&n);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:42:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld ",&p1);
~~~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:44:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld\n",&p2);
~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 5 |
Correct |
12 ms |
9980 KB |
Output is correct |
| 6 |
Correct |
11 ms |
9720 KB |
Output is correct |
| 7 |
Correct |
11 ms |
9976 KB |
Output is correct |
| 8 |
Correct |
11 ms |
9976 KB |
Output is correct |
| 9 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 10 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 11 |
Correct |
11 ms |
9976 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9724 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 5 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 6 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 7 |
Correct |
12 ms |
9900 KB |
Output is correct |
| 8 |
Correct |
11 ms |
9980 KB |
Output is correct |
| 9 |
Correct |
11 ms |
9976 KB |
Output is correct |
| 10 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 11 |
Correct |
11 ms |
9976 KB |
Output is correct |
| 12 |
Correct |
46 ms |
15128 KB |
Output is correct |
| 13 |
Correct |
351 ms |
28808 KB |
Output is correct |
| 14 |
Correct |
127 ms |
15908 KB |
Output is correct |
| 15 |
Correct |
178 ms |
20932 KB |
Output is correct |
| 16 |
Correct |
50 ms |
14728 KB |
Output is correct |
| 17 |
Correct |
153 ms |
28820 KB |
Output is correct |
| 18 |
Correct |
161 ms |
28664 KB |
Output is correct |
| 19 |
Correct |
295 ms |
28344 KB |
Output is correct |
| 20 |
Correct |
57 ms |
15080 KB |
Output is correct |
| 21 |
Correct |
180 ms |
28752 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9720 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9720 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
9720 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
