#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll oo = 2e18;
constexpr int MAXN = 2e5 + 7;
ll translate[MAXN];
vector<pair<ll, ll>> T[MAXN];
pair<ll, ll> input[MAXN];
priority_queue<pair<ll, pair<ll, ll>>> R;
priority_queue<ll> L;
ll LSUM, RSUM;
map<ll, int> mapa;
pair<ll, ll> SUMS[MAXN][2];
ll total;
int k, n, D;
void remove(ll l){
while(L.size() && -(L.top()) <= translate[l]){
LSUM += L.top();
L.pop();
}
}
void updateR(ll l, ll r){
for(auto [a, b] : T[r]){
R.push({a+b, {a, b}});
RSUM += b;
}
while(R.size() && R.top().first >= translate[l] + translate[r]){
L.push(-R.top().second.first);
RSUM -= R.top().second.second;
LSUM += R.top().second.first;
R.pop();
}
remove(l);
}
ll check(ll l, ll r, bool change){
ll res = 0;
priority_queue<pair<ll, pair<ll, ll>>> Rcpy;
priority_queue<ll> Lcpy;
ll LSUMcpy;
ll RSUMcpy;
if(!change){
Rcpy = R;
Lcpy = L;
LSUMcpy = LSUM;
RSUMcpy = RSUM;
}
updateR(l, r);
res += 2*(translate[l]*SUMS[l-1][0].second - SUMS[l-1][0].first);
res += 2*(SUMS[r+1][1].first - translate[r]*SUMS[r+1][1].second);
res += 2*(LSUM - ll(L.size())*translate[l]);
res += 2*(ll(R.size())*translate[r] - RSUM);
if(!change){
R = Rcpy;
L = Lcpy;
LSUM = LSUMcpy;
RSUM = RSUMcpy;
}
return res;
}
ll solve(){
ll best = oo;
int r = 0;
for(int i = 1; i <= D; i++){
while(r < D && (k > 1 || r < i) && (check(i, r+1, 0) <= best || r < i)){
best = min(check(i, ++r, 1), best);
//if(best == 0) cout << "l: " << i << " r: " << r << "\n";
}
remove(i);
}
return best;
}
void scale(){
int act = 0;
for(auto it = mapa.begin(); it != mapa.end(); ++it){
it->second = ++act;
translate[act] = it->second;
}
D = act;
for(int i = 1; i <= n; i++){
if(input[i].first == -1) continue;
input[i].first = mapa[input[i].first];
input[i].second = mapa[input[i].second];
}
}
void compute(){
for(int i = 1; i <= n; i++){
if(input[i].first == -1) continue;
SUMS[input[i].second][0].first += translate[input[i].second];
SUMS[input[i].second][0].second++;
SUMS[input[i].first][1].first += translate[input[i].first];
SUMS[input[i].first][1].second++;
T[input[i].second].push_back({translate[input[i].first], translate[input[i].second]});
}
for(int i = 1; i <= D; i++){
SUMS[i][0].first += SUMS[i-1][0].first;
SUMS[i][0].second += SUMS[i-1][0].second;
}
for(int i = D; i >= 1; i--){
SUMS[i][1].first += SUMS[i+1][1].first;
SUMS[i][1].second += SUMS[i+1][1].second;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 1; i <= n; i++){
char x, y;
ll a, b;
cin >>x >> a >> y >> b;
if(b < a) swap(a, b);
mapa[a];
mapa[b];
if(x != y){
total += (b-a + 1);
input[i] = {a, b};
}
else{
total += (b-a);
input[i] = {-1, -1};
}
}
scale();
compute();
cout << total + solve() << "\n";
}
/*
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8536 KB |
Output is correct |
2 |
Correct |
2 ms |
8536 KB |
Output is correct |
3 |
Correct |
2 ms |
8540 KB |
Output is correct |
4 |
Incorrect |
4 ms |
8940 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8540 KB |
Output is correct |
2 |
Correct |
1 ms |
8536 KB |
Output is correct |
3 |
Correct |
2 ms |
8536 KB |
Output is correct |
4 |
Incorrect |
4 ms |
8796 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8540 KB |
Output is correct |
2 |
Correct |
1 ms |
8672 KB |
Output is correct |
3 |
Incorrect |
2 ms |
8680 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8536 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8536 KB |
Output is correct |
2 |
Correct |
1 ms |
8536 KB |
Output is correct |
3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |