//******************/
//* I<3 C++ */
//* I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//* IN CONTESTS */
//* GET SCORE */
//* AC CODE */
//* LET'S */
//* GO */
//* Written by: */
//* Duc Minh */
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define endl "\n"
#define all1(a) a+1,a+n+1
// #define unordered_map map
// #define push_back emplace_back
// #define gcd(a,b) __gcd(a,b);
// #define lcm(a,b) (a*b)/gcd(a,b);
const long long INF = (long long)1e18;
const long long MOD = (long long)1e9+7;
const long long MODD = 1e9; /// 998244353
const long long maxN = 25009;
///--------------------------------
void solve();
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
file("ducminh");
#endif
// file("tbrackets");
long long t;
// cin >> t;
t=1;
while (t--){
solve();
}
cerr << "Time elapsed: " << TIME << "s.\n";
cerr << "ducminh" << "\n";
return 0;
}
///--------------------[PROBLEM SOLUTION]--------------------///
multiset<long long> ss;
struct Compare {
bool operator() (const long long& a, const long long& b) const {
return a > b;
}
};
long long n,k,a[200009],pre[200009],suf[200009];
multiset<long long,Compare> down;
multiset<long long> up;
long long sum=0,sum1=0,ans=0,sum2=0;
vector<pair<long long,long long>> pp;
void sub1(){
ans=0;
auto it=ss.begin();
if (ss.size()==0) return cout << sum2, void();
advance(it, ss.size()/2);
long long tam=*it;
for (long long x: ss){
ans+=abs(tam-x);
}
ans+=(ss.size()/2);
ans+=sum2;
cout << ans;
}
void sub2(){
if (ss.size()==0) return cout << sum2, void();
vector<int> luu;
for (int x: ss) luu.push_back(x);
// down.insert(a[0]);
// cout <<
for (long long i=0; i<luu.size(); i++){
// if (a[i-k]<*up.begin()) {if (down.size()) down.erase(down.find(a[i-k]));}
// else {if (up.size()) up.erase(up.find(a[i-k]));}
// cout << i << ' ' << a[i-k] << "\n";
if (luu[i]<*up.begin() || up.size()==0) down.insert(luu[i]);
else up.insert(luu[i]);
if (down.size()-up.size()==3){
long long tam=*down.begin();
down.erase(down.begin());
up.insert(tam);
}
if (down.size()-up.size()==2) {
up.insert(*down.begin());
down.erase(down.begin());
}
if (up.size()>down.size()){
long long tam=*up.begin();
up.erase(up.begin());
down.insert(tam);
}
pre[i]=*down.begin();
// cout << i << ": ";
// for (long long x: down) cout << x << ' ';
// cout << "\n";
// for (long long x: up) cout << x << ' ';
// cout << "\n";
}
// for (int i=0; i<luu.size(); i++){
// cout << luu[i] << ' ' << pre[i] << "\n";
// }
down.clear(); up.clear();
for (long long i=luu.size()-1; i>=0; i--){
// if (a[i-k]<*up.begin()) {if (down.size()) down.erase(down.find(a[i-k]));}
// else {if (up.size()) up.erase(up.find(a[i-k]));}
// cout << i << ' ' << a[i-k] << "\n";
if (luu[i]<*up.begin() || up.size()==0) down.insert(luu[i]);
else up.insert(luu[i]);
if (down.size()-up.size()==3){
long long tam=*down.begin();
down.erase(down.begin());
up.insert(tam);
}
if (down.size()-up.size()==2) {
up.insert(*down.begin());
down.erase(down.begin());
}
if (up.size()>down.size()){
long long tam=*up.begin();
up.erase(up.begin());
down.insert(tam);
}
suf[i]=*down.begin();
// cout << i << ':';
// for (long long x: down) cout << x << ' ';
// cout << "\n";
// for (long long x: up) cout << x << ' ';
// cout << "\n";
}
ans=INF;
for (int i=0; i<luu.size()-1; i++){
long long tamans=0;
for (int j=0; j<pp.size(); j++){
long long aa = pp[j].first, bb = pp[j].second;
tamans+=min(abs(aa-pre[i])+abs(bb-pre[i]), abs(aa-suf[i+1])+abs(bb-suf[i+1]));
}
ans=min(ans,tamans);
}
// cout << ans << "\n";
ans+=(ss.size()/2);
ans+=sum2;
cout << ans;
}
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first + a.second < b.first + b.second;
}
void solve(){
long long k,n;
cin >> k >> n;
for (long long i=1; i<=n; i++){
char ch1,ch2;
long long x,y;
cin >> ch1 >> x >> ch2 >> y;
if (ch1!=ch2) {
ss.insert(x); ss.insert(y); pp.push_back({x, y});
sum+=x+y;
}
else sum1+=2,sum2+=abs(y-x);
// pp.push_back({x, y});
}
sort(all(pp),cmp);
if (k==1) sub1();
else sub2();
}
Compilation message
bridge.cpp: In function 'void sub2()':
bridge.cpp:167:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for (long long i=0; i<luu.size(); i++){
| ~^~~~~~~~~~~
bridge.cpp:255:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
255 | for (int i=0; i<luu.size()-1; i++){
| ~^~~~~~~~~~~~~
bridge.cpp:258:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
258 | for (int j=0; j<pp.size(); j++){
| ~^~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:40:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | #define file(name) freopen(name".inp", "r", stdin);\
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:71:9: note: in expansion of macro 'file'
71 | file("ducminh");
| ^~~~
bridge.cpp:41:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:71:9: note: in expansion of macro 'file'
71 | file("ducminh");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
