Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
phalanx
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cctype>
#define N 300020
using namespace std;
int n, m, b;
int x[N], y[N];
long long f[N];
class Node
{
public:
Node *s[2];
long long v;
int w, z;
Node(long long _v, int _w, int _z) : v(_v), w(_w), z(_z)
{
s[0] = s[1] = NULL;
return;
}
int Size(int k)
{
return s[k] ? s[k] -> z : 0;
}
void Update(void)
{
z = Size(0) + Size(1) + w;
return;
}
};
class Splay
{
public:
Node *r;
void RotateSplay(Node *&x, int k)
{
Node *t;
t = x -> s[!k];
x -> s[!k] = t -> s[k];
t -> s[k] = x;
x -> Update();
t -> Update();
x = t;
return;
}
void BuildSplay(Node *&x, int l, int r)
{
int m;
if(l > r)
return;
m = (l + r) / 2;
x = new Node(f[m], 1, 1);
BuildSplay(x -> s[0], l, m - 1);
BuildSplay(x -> s[1], m + 1, r);
x -> Update();
return;
}
void SplaySplay(Node *&x, int k)
{
int t, p;
x -> Update();
t = x -> Size(0) + x -> w;
//printf("go to %d\n, find %d : %d\n", x->v,k,t);
if(k <= t - x -> w)
{
x -> s[0] -> Update();
p = x -> s[0] -> Size(0) + x -> s[0] -> w;
if(k <= p - x -> s[0] -> w)
{
SplaySplay(x -> s[0] -> s[0], k);
RotateSplay(x, 1);
}
else if(k > p)
{
k -= p;
SplaySplay(x -> s[0] -> s[1], k);
RotateSplay(x -> s[0], 0);
}
RotateSplay(x, 1);
}
else if(k > t)
{
k -= t;
x -> s[1] -> Update();
p = x -> s[1] -> Size(0) + x -> s[1] -> w;
if(k <= p - x -> s[1] -> w)
{
SplaySplay(x -> s[1] -> s[0], k);
RotateSplay(x -> s[1], 1);
}
else if(k > p)
{
k -= p;
SplaySplay(x -> s[1] -> s[1], k);
RotateSplay(x, 0);
}
RotateSplay(x, 0);
}
return;
}
Node *GetSplay(Node *x, int k, int &o)
{
int t;
for(o = 0;x;)
{
t = x -> Size(0) + x -> w;
if(k > t)
{
o += t;
k -= t;
x = x -> s[1];
}
else if(k <= t - x -> w)
x = x -> s[0];
else
{
o += t - x -> w;
break;
}
}
return x;
}
void OutputSplay(Node *x)
{
if(!x)return;
printf("(");
OutputSplay(x->s[0]);
printf(")");
printf("%lld",x->v);
printf("(");
OutputSplay(x->s[1]);
printf(")");
}
};
Splay g[N], h;
void Solve(void)
{
int i, c;
long long o;
Node *p, *q;
for(i = 1;i <= n;i ++)
f[i] = (long long)i * m;
h.BuildSplay(h.r, 0, n + 1);
for(i = 1;i <= n;i ++)
{
g[i].r = new Node((long long)(i - 1) * m + 1, m - 1, m - 1);
g[i].r -> s[0] = new Node(0, 1, 1);
g[i].r -> s[1] = new Node(0, 1, 1);
g[i].r -> Update();
}
//OutputSplay(r);puts("");
for(i = 1;i <= b;i ++)
{
//cerr << i << endl;
if(y[i] == m)
{
h.SplaySplay(h.r, x[i]);
h.SplaySplay(h.r -> s[1], (x[i] + 2) - (h.r -> Size(0) + 1));
p = h.r -> s[1] -> s[0];
printf("%lld\n", p -> v);
h.r -> s[1] -> s[0] = NULL;
h.r -> s[1] -> Update();
h.r -> Update();
h.SplaySplay(h.r, n + 1 - 1);
h.r -> s[1] -> s[0] = p;
h.r -> s[1] -> Update();
h.r -> Update();
}
else
{
Splay &s = g[x[i]];
p = s.GetSplay(s.r, y[i] + 1, c);
s.SplaySplay(s.r, c);
s.SplaySplay(s.r -> s[1], (c + p -> w + 1) - (s.r -> Size(0) + s.r -> w));
q = s.r -> s[1] -> s[0];
printf("%lld\n", o = (q -> v + (y[i] - c)));
//cerr<<q -> v + (y[i] - c)<<endl;
if(q -> w == 1)
s.r -> s[1] -> s[0] = NULL;
else if(!(y[i] - c))
{
s.r -> s[1] -> s[0] -> w --;
s.r -> s[1] -> s[0] -> z --;
s.r -> s[1] -> s[0] -> v ++;
}
else if(y[i] - c == q -> w - 1)
{
s.r -> s[1] -> s[0] -> w --;
s.r -> s[1] -> s[0] -> z --;
}
else
{
s.r -> s[1] -> s[0] -> s[1] = new Node(q -> v + (y[i] - c) + 1, q -> w - (y[i] - c) - 1, q -> w - (y[i] - c) - 1);
s.r -> s[1] -> s[0] -> w = y[i] - c;
s.r -> s[1] -> s[0] -> z = y[i] - c;
s.r -> s[1] -> s[0] -> Update();
}
//if(q -> s[1] || q -> s[0])cerr<<"FUCK";
//cerr<<y[i]<<' '<<c<<' '<<q->w<<' '<<q -> w - (y[i] - c) - 1<<endl;
/*s.r -> s[1] -> s[0] -> w = y[i] - c;
s.r -> s[1] -> s[0] -> z = y[i] - c;
s.r -> s[1] -> s[0] -> s[1] = new Node(q -> v + (y[i] - c) + 1, q -> w - (y[i] - c) - 1, q -> w - (y[i] - c) - 1);
s.r -> s[1] -> s[0] -> Update();*/
//cerr<<s.r -> s[1] -> s[0] -> s[1]->v<<' '<<q -> w - (y[i] - c) - 1<<' '<<s.r -> s[1] -> s[0] -> s[1]->w<<' '<<s.r -> s[1] -> s[0] -> s[1]->z<<endl;
s.r -> s[1] -> Update();
s.r -> Update();
h.SplaySplay(h.r, x[i]);
h.SplaySplay(h.r -> s[1], (x[i] + 2) - (h.r -> Size(0) + 1));
s.SplaySplay(s.r, m - 1);
s.r -> s[1] -> s[0] = new Node(h.r -> s[1] -> s[0] -> v, 1, 1);
s.r -> s[1] -> Update();
s.r -> Update();
h.r -> s[1] -> s[0] = NULL;
h.r -> s[1] -> Update();
h.r -> Update();
h.SplaySplay(h.r, n + 1 - 1);
h.r -> s[1] -> s[0] = new Node(o, 1, 1);
h.r -> s[1] -> Update();
h.r -> Update();
}
}
return;
}
int Scan(void)
{
int s;
char c;
for(s = 0;(c = getchar()) != EOF && !isdigit(c);)
;
do
s = s * 10 + c - 48;
while((c = getchar()) != EOF && isdigit(c));
return s;
}
int main() //phalanx.cpp
{
int i;
freopen("phalanx.in" , "r", stdin );
freopen("phalanx.out", "w", stdout);
n = Scan();
m = Scan();
b = Scan();
for(i = 1;i <= b;i ++)
{
x[i] = Scan();
y[i] = Scan();
}
Solve();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.