Submission #213057

#	Time	Username	Problem	Language	Result	Execution time	Memory
213057		qkxwsm	Sweeping (JOI20_sweeping)	C++14	0 / 100	1955 ms	71800 KiB

sweeping

#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

mt19937 rng(69);
template<class T>
T randomize(T mod)
{
    return uniform_int_distribution<T>(0, mod - 1)(rng);
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 1500013;
const int INF = 1000000007;

int N, M, Q;

bool cmp(pii a, pii b)
{
    return (a.fi <= b.fi && a.se >= b.se);
}

struct node
{
    node *ch[2], *p;
    pii pos, lazy;
    int pri;
    node(int x, int y)
    {
        pos = {x, y};
        lazy = {-1, -1};
        pri = randomize(INF);
    }
};

void push(node *t)
{
    if (!t) return;
    if (t -> lazy == MP(-1, -1)) return;
    ckmax(t -> pos.fi, t -> lazy.fi);
    ckmax(t -> pos.se, t -> lazy.se);
    if (t -> ch[0])
    {
        ckmax(t -> ch[0] -> lazy.fi, t -> lazy.fi);
        ckmax(t -> ch[0] -> lazy.se, t -> lazy.se);
        assert(t -> ch[0] -> p == t);
    }
    if (t -> ch[1])
    {
        ckmax(t -> ch[1] -> lazy.fi, t -> lazy.fi);
        ckmax(t -> ch[1] -> lazy.se, t -> lazy.se);
        assert(t -> ch[1] -> p == t);
    }
    t -> lazy = {-1, -1};
    return;
}
typedef pair<node*, node*> pnn;
pnn split(node* t, int v, bool dir)
{
    //v goes to the right tho...
    if (!t) return {nullptr, nullptr};
    push(t);
    // cerr << t -> pos.fi << ',' << t -> pos.se << ' ' << t -> pri << endl;
    if ((!dir && t -> pos.fi > v) || (dir && t -> pos.se < v))
    {
        // cerr << "left\n";
        if (t -> ch[0]) t -> ch[0] -> p = nullptr;
        pnn p = split(t -> ch[0], v, dir);
        t -> ch[0] = p.se; if (t -> ch[0]) t -> ch[0] -> p = t;
        return {p.fi, t};
    }
    else
    {
        // cerr << "right\n";
        if (t -> ch[1]) t -> ch[1] -> p = nullptr;
        pnn p = split(t -> ch[1], v, dir);
        t -> ch[1] = p.fi; if (t -> ch[1]) t -> ch[1] -> p = t;
        return {t, p.se};
    }
}
node *merge(node *l, node *r)
{
    push(l); push(r);
	if (!l) return r;
	if (!r) return l;
    assert(l != r);
	if (l -> pri > r -> pri)
	{
		l -> ch[1] = merge(l -> ch[1], r); if (l -> ch[1]) l -> ch[1] -> p = l;
	    return l;
	}
	else
	{
		r -> ch[0] = merge(l, r -> ch[0]); if (r -> ch[0]) r -> ch[0] -> p = r;
		return r;
	}
}
void get(node *t)
{
    vector<node*> vn;
    while(t)
    {
        vn.PB(t);
        t = t -> p;
    }
    reverse(ALL(vn));
    for (auto w : vn)
    {
        push(w);
    }
}
void inorder(node *t)
{
    if (!t) return;
    push(t);
    inorder(t -> ch[0]);
    cerr << t -> pos.fi << ',' << t -> pos.se << ',' << t -> pri << ' ';
    inorder(t -> ch[1]);
}
void preorder(node *t)
{
    if (!t) return;
    push(t);
    cerr << t -> pos.fi << ',' << t -> pos.se << ',' << t -> pri << ' ';
    preorder(t -> ch[0]);
    preorder(t -> ch[1]);
}

node *root;
node *V[MAXN];

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M >> Q;
    FOR(i, 0, M)
    {
        pii p;
        cin >> p.fi >> p.se;
        V[i] = new node(p.fi, p.se);
        root = merge(root, V[i]);
        // cerr << "i = " << i << endl;
    }
    while(Q--)
    {
        // inorder(root); cerr << endl;
        int typ, idx;
        cin >> typ >> idx;
        // cerr << "QUERY " << typ << ' ' << idx << endl;
        if (typ == 1)
        {
            idx--;
            // cerr << "idx = " << idx << endl;
            get(V[idx]);
            pii p = V[idx] -> pos;
            cout << p.fi << ' ' << p.se << '\n';
        }
        if (typ == 2)
        {
            pnn p = split(root, idx + 1, true), p1 = split(p.se, N - idx, false);
            // inorder(p1.fi); cerr << endl;
            // cerr << "N - idx = " << N - idx << endl;
            if (p1.fi)
            {
                p1.fi -> lazy.fi = N - idx;
            }
            root = merge(p.fi, merge(p1.fi, p1.se));
            //push shit horizontally.
            //everything with x <= N-idx and y <= idx gets pushed to x=N-idx.
        }
        if (typ == 3)
        {
            pnn p = split(root, N - idx, true), p1 = split(p.se, idx + 1, false);
            if (p1.fi)
            {
                p1.fi -> lazy.se = N - idx;
            }
            //push shit vertically
            //everything with x <= idx && y <= N-idx gets pushed to y = N-idx.
            root = merge(p.fi, merge(p1.fi, p1.se));
        }
    }
    return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25