没有数据,问一下能不能给个一组小的数据
#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define mod 1000000
const int maxn = 1e6+100;
using namespace std;
struct fhqtreap{
int Total;
int Rt;
struct node{
int key;
int ls, rs, sz, priority;
}Tree[maxn];
void pushup(int idx) {
if(idx != 0) {
Tree[idx].sz = Tree[Tree[idx].ls].sz+Tree[Tree[idx].rs].sz+1;
}
}
int creat(int key) {
int Rt = ++Total;
Tree[Rt].key = key;
Tree[Rt].sz = 1;
Tree[Rt].ls = Tree[Rt].rs = 0;
Tree[Rt].priority = rand();
return Rt;
}
void split(int Rt, int key, int &x, int &y) {
if (Rt == 0) {
x = y = 0; return;
}
if (Tree[Rt].key <= key) {
x = Rt;
split(Tree[Rt].rs, key, Tree[Rt].rs, y);
} else {
y = Rt;
split(Tree[Rt].ls, key, x, Tree[Rt].ls);
}
pushup(Rt);
}
int merge(int x, int y) {
if(x==0 or y==0) return x|y;
if(Tree[x].priority > Tree[y].priority) {
Tree[x].rs = merge(Tree[x].rs, y);
pushup(x);
return x;
} else {
Tree[y].ls = merge(x, Tree[y].ls);
pushup(y);
return y;
}
}
void insert(int key) {
int x, y;
split(Rt, key-1, x, y);
Rt = merge(merge(x, creat(key)),y);
}
int findmax(int idx) {
if(Tree[idx].rs) {
return findmax(Tree[idx].rs);
}
return Tree[idx].key;
}
int findmin(int idx) {
if(Tree[idx].ls) {
return findmax(Tree[idx].ls);
}
return Tree[idx].key;
}
int Lowerbound(int idx, int key) {
if(Tree[idx].key >= key) {
if(!Tree[idx].ls) return Tree[idx].key;
return min(Lowerbound(Tree[idx].ls, key), Tree[idx].key);
} else {
if(!Tree[idx].rs) return inf;
return Lowerbound(Tree[idx].rs, key);
}
}
int lowerbound(int key) {
return Lowerbound(Rt, key);
}
void del(int key) {
int T1, T2, T3;
split(Rt, key, T1, T2);
split(T1, key-1, T1, T3);
Rt = merge(T1, T2);
}
int rk(int key) {
int T1, T2;
split(Rt, key, T1, T2);
int k = Tree[T1].sz;
Rt = merge(T1, T2);
return k+1;
}
};
fhqtreap fhq;
int n, now, big;
int ans = 0;
void work(int x) {
if(x >= fhq.findmax(fhq.Rt)) {
ans += x - fhq.findmax(fhq.Rt);
fhq.del(fhq.findmax(fhq.Rt));
} else if(x <= fhq.findmin(fhq.Rt)){
ans += fhq.findmin(fhq.Rt) - x;
fhq.del(fhq.findmin(fhq.Rt));
} else {
int a = fhq.lowerbound(x);
int b = x - (a - x);
int c = fhq.lowerbound(b);
if(c >= x) {
ans += c - x;
fhq.del(c);
} else {
if(x - c <= a - x) {
ans += x-c;
fhq.del(c);
} else {
ans += a-x;
fhq.del(a);
}
}
}
}
signed main() {
srand(time(0));
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i=1; i<=n; ++i) {
int bl, x; cin >> bl >> x;
if(big == 0) {
now = bl; fhq.insert(x); ++ big;
} else {
if(now == bl) {
fhq.insert(x); ++ big;
} else {
work(x); -- big;
}
}
}
cout << ans % mod;
return 0;
}