#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
int k, n;
vector<pp> d;
ll ans_base;
void in(){
read(k, n);
for(int i=1; i<=n; ++i){
char p, q;
int s, t;
auto f = [](){char t; do{t=getchar();}while(t!='A'&&t!='B'); return t;};
p = f(); read(s);
q = f(); read(t);
if(p == q){
ans_base += abs(s - t);
} else {
++ans_base;
d.eb(min(s, t), max(s, t));
}
}
n = d.size();
}
ll dp1[100010];
ll dp2[100010];
struct SEG {
const static int M = 262144;
ll tree[M<<1];
void init(){ memset(tree, 0, sizeof(tree)); }
void upd(int p, ll v){for(p+=M;p;p/=2)tree[p]+=v;}
ll s(int l,int r){
ll ret=0;
l+=M; r+=M;
while(l<=r){
if(l&1) ret+=tree[l++];
if(r%2==0) ret+=tree[r--];
l>>=1; r>>=1;
}
return ret;
}
} sc, sl, sr;
vector<int> pt;
priority_queue<int> pq;
void Work(ll dp[100010]){
sc.init();
sl.init();
sr.init();
while(pq.size()) pq.pop();
auto add = [&](int a){
pq.push(a);
int b = lower_bound(all(pt), a) - pt.begin();
sc.upd(b, 1);
sl.upd(b, -a);
sr.upd(b, a);
};
for(int i=1; i<=n; ++i){
add(d[i-1].x);
add(d[i-1].y);
pq.pop();
int mid = pq.top();
int p = lower_bound(all(pt), mid) - pt.begin();
dp[i] = sc.s(0, p-1) * mid + sl.s(0, p-1) +
sr.s(p+1, pt.size()-1) - sc.s(p+1, pt.size()-1) * mid;
}
}
int main()
{
in();
for(auto tmp:d) pt.pb(tmp.x), pt.pb(tmp.y);
sort(all(pt));
if(k == 1){
ll ans=0; int p=pt[n];
for(auto tmp:d) ans += abs(tmp.x-p) + abs(tmp.y-p);
printf("%lld\n", ans + ans_base);
return 0;
}
pt.erase(unique(all(pt)), pt.end());
sort(all(d), [&](const pp& a, const pp& b){
return a.x+a.y < b.x+b.y;
});
Work(dp1);
reverse(all(d));
Work(dp2); reverse(dp2, dp2+n+1);
ll ans = 1LL << 60;
for(int i=0; i<=n; ++i){
ans = min(ans, dp1[i] + dp2[i]);
}
printf("%lld\n", ans + ans_base);
return 0;
}
Compilation message
bridge.cpp: In function 'void read(int&)':
bridge.cpp:6:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void read(int& x){ scanf("%d",&x); }
^
bridge.cpp: In function 'void read(ll&)':
bridge.cpp:7:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void read(ll& x){ scanf("%lld",&x); }
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
15876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
15876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15876 KB |
Output is correct |
| 2 |
Correct |
3 ms |
15876 KB |
Output is correct |
| 3 |
Correct |
3 ms |
15876 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
15876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
15876 KB |
Output is correct |
| 2 |
Correct |
0 ms |
15876 KB |
Output is correct |
| 3 |
Correct |
3 ms |
15876 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
15876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
15876 KB |
Output is correct |
| 2 |
Correct |
0 ms |
15876 KB |
Output is correct |
| 3 |
Correct |
9 ms |
15876 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
15876 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
