F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 1208 >> 求解 疯狂TLE 但是在某oj过了
33511595 @ 2017-12-09 00:29:15
[ Quote ] [ Edit ] [ Delete ] 1#
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
inline void swap(int &a, int &b)
{
int tmp = a;a = b;b = tmp;
}

const int INF = 0x3f3f3f3f;
const int MAXN = 2000000 + 10;
const int MOD = 1000000;

int fa[MAXN], size[MAXN], data[MAXN], cnt[MAXN], ch[MAXN][2], root, nn;
int son(int x){return x == ch[fa[x]][1];}
void pushup(int rt)
{
int l = ch[rt][0], r = ch[rt][1];
size[rt] = size[l] + size[r] + cnt[rt];
}
void rotate(int x)
{
int y = fa[x], z = fa[y], b = son(x), c = son(y), a = ch[x][!b];
if(z) ch[z][c] = x; else root = x; fa[x] = z;
if(a) fa[a] = y; ch[y][b] = a;
ch[x][!b] = y,fa[y] = x;
pushup(y),pushup(x);
}
void splay(int x, int i)
{
while(fa[x] != i)
{
int y = fa[x], z = fa[y];
if(z == i) rotate(x);
else
if(son(x) == son(y))rotate(y), rotate(x);
else rotate(x), rotate(x);
}
}
void insert(int &rt, int x)
{
if(rt == 0)
{
rt = ++nn, data[nn] = x, size[nn] = cnt[nn] = 1;
return;
}
if(data[rt] == x)
{
++cnt[rt], ++size[rt];
return;
}
if(x < data[rt]) insert(ch[rt][0], x), fa[ch[rt][0]] = rt, pushup(rt);
else insert(ch[rt][1], x), fa[ch[rt][1]] = rt, pushup(rt);
}
int getpre(int rt, int x)
{
int p = rt, ans = -1;
while(p)
{
if(x < data[p]) p = ch[p][0];
else ans = p, p = ch[p][1];
}
return ans;
}
int getnxt(int rt, int x)
{
int p = rt, ans = -1;
while(p)
{
if(x > data[p]) p = ch[p][1];
else ans = p, p = ch[p][0];
}
return ans;
}
int getmn(int rt)
{
int p = rt, ans = -1;
while(p)
{
ans = p, p = ch[p][0];
}
return ans;
}
void del(int rt, int x)
{
if(data[rt] == x)
{
if(cnt[rt] > 1) -- cnt[rt], -- size[rt];
else
{
splay(rt, 0);
int p = getmn(ch[rt][1]);
if(p != -1)
{
splay(p, rt);
root = p, fa[p] = 0, ch[p][0] = ch[rt][0], fa[ch[rt][0]] = p;
pushup(p);
}
else root = ch[rt][0], fa[ch[rt][0]] = 0;
}
return;
}
if(x < data[rt]) del(ch[rt][0], x);
else del(ch[rt][1], x);
pushup(rt);
}
int n,tot;
long long ans;

int main()
{
freopen("data.txt", "r", stdin);
scanf("%d", &n);
int flag = -1;
for(register int i = 1;i <= n;++ i)
{
int a,b;
if(scanf("%d%d", &a, &b) == EOF) break;
if(a == flag)
{
insert(root, b);
++ tot;
continue;
}
else if(flag == -1)
{
flag = a;
insert(root, b);
++ tot;
continue;
}
else -- tot;
if(tot == 0) flag = -1;
int pre = getpre(root, b), nxt = getnxt(root, b);
if(pre == -1 && nxt == -1) continue;
else if(pre == -1)
{
ans += abs(b - data[nxt]) % MOD;
if(ans >= MOD) ans -= MOD;
del(root, data[nxt]);
}
else if(nxt == -1)
{
ans += abs(b - data[pre]) % MOD;
if(ans >= MOD) ans -= MOD;
del(root, data[pre]);
}
else if(abs(b - data[nxt]) < abs(b - data[pre]))
{
ans += abs(b - data[nxt]) % MOD;
if(ans >= MOD) ans -= MOD;
del(root, data[nxt]);
}
else
{
ans += abs(b - data[pre]) % MOD;
if(ans >= MOD) ans -= MOD;
del(root, data[pre]);
}
}
printf("%lld", ans);
return 0;
}
fengchanghn @ 2017-12-11 09:03:23
[ Quote ] [ Edit ] [ Delete ] 2#
bzoj 本来就慢啊
[Top] [Previous Page] [Next Page]

HOME Back