This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long long ll;
#define int long long
#define sz(x) (int)(x.size())
#define debug(x) cerr << (#x) << ": " << (x) << endl
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
struct node {
int left, right;
int sum, nb;
node() {left=-1, right=-1, sum=0, nb=0;}
};
vector<vector<node>> st(2);
void create(int empl) {
st[empl].push_back(node());
}
void updatte(int empl, int node) {
int nb=0, sum=0;
if (st[empl][node].left!=-1) nb+=st[empl][ st[empl][node].left ].nb, sum+=st[empl][ st[empl][node].left ].sum;
if (st[empl][node].right!=-1) nb+=st[empl][ st[empl][node].right ].nb, sum+=st[empl][ st[empl][node].right ].sum;
st[empl][node].nb=nb, st[empl][node].sum=sum;
}
void update(int empl, int node, int left, int right, int qval, int value) {
if (left==right) {
st[empl][node].nb+=value;
st[empl][node].sum+=value*left;
return;
}
int mid=(left+right)/2;
if (mid>=qval) {
if (st[empl][node].left==-1) {
create(empl);
st[empl][node].left=sz(st[empl])-1;
}
update(empl, st[empl][node].left, left, mid, qval, value);
} else {
if (st[empl][node].right==-1) {
create(empl);
st[empl][node].right=sz(st[empl])-1;
}
update(empl, st[empl][node].right, mid+1, right, qval, value);
}
updatte(empl, node);
}
int milieu;
int query(int empl, int node, int left, int right, int qval) {
if (left==right) {
milieu=left;
return 0;
}
int mid=(left+right)/2;
int ans=0;
if (st[empl][node].left!=-1 && st[empl][ st[empl][node].left ].nb>=qval) {
ans=query(empl, st[empl][node].left, left, mid, qval);
if (st[empl][node].right!=-1) {
ans+=st[empl][ st[empl][node].right ].sum-st[empl][ st[empl][node].right ].nb*milieu;
}
} else if (st[empl][node].right!=-1) {
int moins=0;
if (st[empl][node].left!=-1) moins=st[empl][ st[empl][node].left].nb;
ans=query(empl, st[empl][node].right, mid+1, right, qval-moins);
if (st[empl][node].left!=-1) {
ans+=st[empl][ st[empl][node].left ].nb*milieu-st[empl][ st[empl][node].left ].sum;
}
}
return ans;
}
struct traj {
int l, r;
double mid;
};
vector<traj> a;
int n, k, m;
void solve() {
cin >> k >> n;
int res=0;
for (int i=0; i<n; i++) {
char aa, bb;
int aaa, bbb; cin >> aa >> aaa >> bb >> bbb;
if (aa==bb) {
res+=abs(aaa-bbb);
continue;
}
if (aaa>bbb) swap(aaa, bbb);
a.push_back(traj{aaa, bbb, (double)(aaa+bbb)/2.0});
}
n=sz(a);
res+=n;
if (n==0) {
cout << res << endl;
return;
}
sort(all(a), [](traj &A, traj &B){return A.mid<B.mid;});
create(0), create(1);
for (int i=0; i<n; i++) {
update(0, 0, 0, (int)1e9, a[i].l, 1);
update(0, 0, 0, (int)1e9, a[i].r, 1);
}
if (k==1) {
cout << res+query(0, 0, 0, (int)1e9, n) << endl;
return;
}
int ans=LLONG_MAX;
for (int i=0; i<n; i++) {
int s1=query(0, 0, 0, (int)1e9, (n-i));
int s2=query(1, 0, 0, (int)1e9, i);
ans=min(ans, s1+s2);
update(0, 0, 0, (int)1e9, a[i].l, -1);
update(0, 0, 0, (int)1e9, a[i].r, -1);
update(1, 0, 0, (int)1e9, a[i].l, 1);
update(1, 0, 0, (int)1e9, a[i].r, 1);
}
cout << res+ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt=1;// cin >> tt;
while(tt--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |