#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define name "main"
typedef pair<int,int> ii;
#define fi first
#define se second
const int N=(int)1e5;
bool print=false;
vector<ii>sett;
vector<int>nen;
int n,k,cnt=0;
ll f[N+2];
bool used[N*2+2];
bool cmp(ii a,ii b){
return a.fi+a.se<b.fi+b.se;
}
class BIT{
public:
vector<ll>tot;
vector<int> cnt,one;
int n;
void init(int _n){
n=_n;
tot.assign(_n+2,0);
cnt.assign(_n+2,0);
one.assign(_n+2,0);
return;
}
void upd_tot(int id,int val){
for(;id<=n;id+=(id&(-id)))
tot[id]+=val;
return;
}
void upd_cnt(int id,int val){
for(;id<=n;id+=(id&(-id)))
cnt[id]+=val;
return;
}
void upd_one(int id,int val){
for(;id<=n;id+=(id&(-id)))
one[id]+=val;
}
int Get_tot(int id){
ll sum=0;
for(;id;id-=(id&(-id)))
sum+=tot[id];
return sum;
}
ll Get_cnt(int id){
ll sum=0;
for(;id;id-=(id&(-id)))
sum+=cnt[id];
return sum;
}
ll Get_one(int id){
ll sum=0;
for(;id;id-=(id&(-id)))
sum+=one[id];
return sum;
}
ll sum_range(int t,int l,int r){
if (t==1){
return Get_tot(r)-Get_tot(l-1);
}
if (t==2){
return Get_cnt(r)-Get_cnt(l-1);
}
if (t==3){
return Get_one(r)-Get_one(l-1);
}
}
};
BIT tree;
ll F(int i){
int l=1,r=nen.size(),p=1;
while(l<=r){
int m=(l+r)>>1;
if (tree.sum_range(3,1,m)<=(cnt+1)/2){
l=m+1,p=m;
}
else r=m-1;
}
p--;
return nen[p]*tree.sum_range(2,1,p)-tree.sum_range(1,1,p) + tree.sum_range(1,p+1,nen.size())-nen[p]*tree.sum_range(2,p+1,nen.size()) + i;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>k>>n;
ll ans=0;
for (int i=1;i<=n;++i){
char c1,c2; int a,b;
cin>>c1>>a>>c2>>b;
if (c1==c2) ans+=abs(a-b);
else {
nen.push_back(a);
nen.push_back(b);
sett.push_back({a,b});
}
}
sort(nen.begin(),nen.end()); nen.resize(unique(nen.begin(),nen.end())-nen.begin());
sort(sett.begin(),sett.end(),cmp);
tree.init(nen.size());
for (int i=1;i<=sett.size();++i){
int a=sett[i-1].fi,b=sett[i-1].se;
a=upper_bound(nen.begin(),nen.end(),a)-nen.begin();
b=upper_bound(nen.begin(),nen.end(),b)-nen.begin();
tree.upd_cnt(a,1),tree.upd_cnt(b,1);
tree.upd_tot(a,nen[a-1]),tree.upd_tot(b,nen[b-1]);
if (!used[a]) used[a]=true,tree.upd_one(a,1),++cnt;
if (!used[b]) used[b]=true,tree.upd_one(b,1),++cnt;
f[i]=F(i);
}
if (k==1) ans=ans+f[sett.size()];
cout<<ans;
exit(0);
}
Compilation message
bridge.cpp: In function 'int32_t main()':
bridge.cpp:111:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i=1;i<=sett.size();++i){
| ~^~~~~~~~~~~~~
bridge.cpp: In member function 'll BIT::sum_range(int, int, int)':
bridge.cpp:76:2: warning: control reaches end of non-void function [-Wreturn-type]
76 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
504 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
