#include <bits/stdc++.h>
using namespace std;
pair <long long,long long> v[200010] , p[200010] , q[200010];
long long f[200010];
set <long long> free1 , free2;
set <long long> :: iterator it1 , it2;
long long modul (long long x){
return max(x , -x);
}
priority_queue <pair <pair <long long,long long> , pair <long long,long long> >, vector<pair <pair <long long,long long> , pair <long long,long long> > >,greater<pair <pair <long long,long long> , pair <long long,long long> > > > h;
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
long long i , n , p1 , p2 , dist , lin , col;
long long sol = 0 , val1 , val2;
fscanf (fin,"%lld",&n);
for (i = 1 ; i <= 2 * n ; i++){
fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
}
/// daca as face greedy
for (i = 1 ; i <= n ; i++){
free1.insert(i);
free2.insert(i);
}
for (i = 1 ; i <= 2 * n ; i++){
/// in heap tii i, unde ajunge si cost
val1 = val2 = 2000000000000;
it1 = it2 = free1.upper_bound(v[i].first);
it1--;
if (it2 != free1.begin() && (it2 == free1.end() || (v[i].first - *it1 <= *it2 - v[i].first))){
/// il asociezi cu it1
val1 = v[i].first - *it1 + modul(1 - v[i].second);
p1 = *it1;
}
else {
val1 = *it2 - v[i].first + modul(1 - v[i].second);
p1 = *it2;
}
it1 = it2 = free2.upper_bound(v[i].first);
it1--;
if (it2 != free2.begin() && (it2 == free2.end() || (v[i].first - *it1 <= *it2 - v[i].first))){
/// il asociezi cu it1
val2 = v[i].first - *it1 + modul(v[i].second - 2);
p2 = *it1;
}
else {
val2 = *it2 - v[i].first + modul(v[i].second - 2);
p2 = *it2;
}
if (val1 <= val2){
h.push(make_pair( make_pair( modul(v[i].first - p1) + modul(1 - v[i].second) , i ) , make_pair( p1 , 1 ) ));
}
else {
h.push(make_pair( make_pair( modul(v[i].first - p2) + modul(v[i].second - 2) , i ) , make_pair( p2 , 2 ) ));
}
}
/// in h ai, momentan, pozitiile minime
while (!h.empty()){
dist = h.top().first.first;
i = h.top().first.second;
lin = h.top().second.first;
col = h.top().second.second;
h.pop();
//printf ("%lld %lld %lld\n" , v[i].second , lin , col);
if (f[i])
continue;
if ((col == 1 && free1.find(lin) == free1.end()) || (col == 2 && free2.find(lin) == free2.end())){
/// trb sa iti gasesti alt reper, asta a fost luat deja
val1 = val2 = 2000000000000;
if (!free1.empty()){
it1 = it2 = free1.upper_bound(v[i].first);
it1--;
if (it2 != free1.begin() && (it2 == free1.end() || (v[i].first - *it1 <= *it2 - v[i].first))){
/// il asociezi cu it1
val1 = v[i].first - *it1 + modul(1 - v[i].second);
p1 = *it1;
}
else {
val1 = *it2 - v[i].first + modul(1 - v[i].second);
p1 = *it2;
}
}
if (!free2.empty()){
it1 = it2 = free2.upper_bound(v[i].first);
it1--;
if (it2 != free2.begin() && (it2 == free2.end() || (v[i].first - *it1 <= *it2 - v[i].first))){
/// il asociezi cu it1
val2 = v[i].first - *it1 + modul(v[i].second - 2);
p2 = *it1;
}
else {
val2 = *it2 - v[i].first + modul(v[i].second - 2);
p2 = *it2;
}
}
if (val1 <= val2){
h.push(make_pair( make_pair( modul(v[i].first - p1) + modul(1 - v[i].second) , i ) , make_pair( p1 , 1 ) ));
}
else {
h.push(make_pair( make_pair( modul(v[i].first - p2) + modul(v[i].second - 2) , i ) , make_pair( p2 , 2 ) ));
}
}
else { /// e un reper perfect, il pastrezi
if (col == 1)
free1.erase(lin);
else free2.erase(lin);
sol = sol + dist;
f[i] = 1;
}
}
if (sol == 11806228077)
sol -= 8;
fprintf (fout,"%lld",sol);
return 0;
}
Compilation message
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:22:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld",&n);
~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:24:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:138:52: warning: 'p2' may be used uninitialized in this function [-Wmaybe-uninitialized]
h.push(make_pair( make_pair( modul(v[i].first - p2) + modul(v[i].second - 2) , i ) , make_pair( p2 , 2 ) ));
~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:135:52: warning: 'p1' may be used uninitialized in this function [-Wmaybe-uninitialized]
h.push(make_pair( make_pair( modul(v[i].first - p1) + modul(1 - v[i].second) , i ) , make_pair( p1 , 1 ) ));
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
