#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define int long long
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define v vector
#define f first
#define s second
const int mod = 1e9+7;
v<int> fac(200005,1);
int fp(int b,int r) {
if (r==0) {
return 1;
} else if (r==1) {
return b;
}
int a=fp(b,r/2);
return a*a%mod*((r%2)?b:1)%mod;
}
int ncr(int n,int r) {
if (n<r) {
return 0;
}
return (fac[n]*fp(fac[n-r]*fac[r]%mod,mod-2))%mod;
}
int sqrt(int n) {
int l=0,r=1e9,m;
while (l<r) {
m=(l+r)>>1;
if (m*m>=n) {
r=m;
} else {
l=m+1;
}
}
return l;
}
multiset<int> a1,a2,b1,b2;
signed main() {
for (int i=1;i<=200000;i++) {
fac[i]=fac[i-1]*i%mod;
}
int k,n;
cin >> k>>n;
int r=0;
v<pair<int,int>> p;
int x,y;
char z,w;
for (int i=0;i<n;i++) {
cin >> z>>x>>w>>y;
if (z==w) {
r+=abs(x-y);
} else {
if (x<y) {
y^=x;
x^=y;
y^=x;
}
p.push_back({x,y});
}
}
sort(be(p));
if (k==1) {
int sum1=0,sum2=0;
for (auto [p1,p2]:p) {
int a[2]={p1,p2};
for (int i=0;i<2;i++) {
if (a1.empty()) {
sum1+=a[i];
a1.insert(a[i]);
} else {
if (a[i] > *a1.rbegin()) {
sum2+=a[i];
a2.insert(a[i]);
if (a2.size()>a1.size()) {
int f=*a2.begin();
sum2-=f;
sum1+=f;
a1.insert(f);
a2.erase(f);
}
} else {
sum1+=a[i];
a1.insert(a[i]);
if (a1.size()-a2.size()>(a1.size()+a2.size())%2) {
int f=*a1.rbegin();
sum2+=f;
sum1-=f;
a2.insert(f);
a1.erase(f);
}
}
}
}
}
cout << r+sum2-sum1+((n%2)?*a1.rbegin():0);
return 0;
}
/*n=p.size();
int sum00=0,sum10=0,sum01=0,sum11=0;
for (auto [p1,p2]:p) {
if (b1.empty()) {
sum10+=p1;
b1.insert(p1);
} else {
if (p1 > *b1.rbegin()) {
sum11==p1;
b2.insert(p1);
if (b2.size()>b1.size()) {
int f=*b2.begin();
sum10+=f;
sum11-=f;
b1.insert(f);
b2.erase(f);
}
} else {
b1.insert(p1);
if (b1.size()-b2.size()>(b1.size()+b2.size())%2) {
int f=*b1.rbegin();
sum10-=f;
sum11+=f;
b2.insert(f);
b1.erase(f);
}
}
}
if (b1.empty()) {
b1.insert(p2);
} else {
if (p2 > *b1.rbegin()) {
b2.insert(p2);
if (b2.size()>b1.size()) {
int f=*b2.begin();
sum10+=f;
sum11-=f;
b1.insert(f);
b2.erase(f);
}
} else {
b1.insert(p2);
if (b1.size()-b2.size()>(b1.size()+b2.size())%2) {
int f=*b1.rbegin();
sum10-=f;
sum11+=f;
b2.insert(f);
b1.erase(f);
}
}
}
}
for (auto [p1,p2]:p) {
}*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
3676 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
3676 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
