Submission #213159

#	Time	Username	Problem	Language	Result	Execution time	Memory
213159		qkxwsm	Sweeping (JOI20_sweeping)	C++14	64 / 100	4048 ms	176848 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 = 1000013;
const int INF = 1000000007;

int N, M, Q;

int indexof(int v, vi &vec)
{
    return UB(ALL(vec), v) - vec.begin() - 1;
}

bool cmp(pii a, pii b)
{
    return MP(a.fi, -a.se) > MP(b.fi, -b.se);
}

struct node
{
    node *ch[2], *p;
    pii pos, lazy;
    int pri;
    node(int x, int y)
    {
        ch[0] = nullptr;
        ch[1] = nullptr;
        p = nullptr;
        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);
    if ((!dir && t -> pos.fi > v) || (dir && t -> pos.se < v))
    {
        pnn p = split(t -> ch[0], v, dir);
        t -> ch[0] = p.se; if (t -> ch[0]) t -> ch[0] -> p = t;
        if (p.fi) p.fi -> p = nullptr;
        return {p.fi, t};
    }
    else
    {
        pnn p = split(t -> ch[1], v, dir);
        t -> ch[1] = p.fi; if (t -> ch[1]) t -> ch[1] -> p = t;
        if (p.se) p.se -> p = nullptr;
        return {t, p.se};
    }
}
pnn Split(node *t, pii v)
{
    if (!t) return {nullptr, nullptr};
    push(t);
    if (cmp(t -> pos, v))
    {
        pnn p = Split(t -> ch[0], v);
        t -> ch[0] = p.se; if (t -> ch[0]) t -> ch[0] -> p = t;
        if (p.fi) p.fi -> p = nullptr;
        return {p.fi, t};
    }
    else
    {
        pnn p = Split(t -> ch[1], v);
        t -> ch[1] = p.fi; if (t -> ch[1]) t -> ch[1] -> p = t;
        if (p.se) p.se -> p = nullptr;
        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]);
}

node *root;
node *V[MAXN];

void ins(int x, int y, int idx)
{
    // inorder(root); cerr << endl;
    // cerr << "insert " << x << ' ' << y << endl;
    V[idx] = new node(x, y);
    pnn p = Split(root, {x, y});
    // cerr << "ok" << endl;
    root = merge(p.fi, merge(V[idx], p.se));
}

struct segtree
{
    int seg[2 * MAXN];
    priority_queue<pii, vector<pii>, greater<pii> > pts[MAXN];
    vi res;
    void build(int w, int L, int R)
    {
        if (L == R)
        {
            seg[w] = (pts[L].empty() ? INF : pts[L].top().fi);
            return;
        }
        int mid = (L + R) >> 1;
        build(w << 1, L, mid);
        build(w << 1 | 1, mid + 1, R);
        seg[w] = min(seg[w << 1], seg[w << 1 | 1]);
    }
    void walk(int w, int L, int R, int a, int b, int v)
    {
        if (b < L || R < a || seg[w] > v) return;
        if (L == R)
        {
            while(!pts[L].empty() && pts[L].top().fi <= v)
            {
                res.PB(pts[L].top().se);
                pts[L].pop();
            }
            seg[w] = (pts[L].empty() ? INF : pts[L].top().fi);
            return;
        }
        int mid = (L + R) >> 1;
        walk(w << 1, L, mid, a, b, v);
        walk(w << 1 | 1, mid + 1, R, a, b, v);
        seg[w] = min(seg[w << 1], seg[w << 1 | 1]);
        return;
    }
    int query(int w, int L, int R, int a, int b)
    {
        if (a <= L && R <= b) return seg[w];
        int mid = (L + R) >> 1;
        if (b <= mid) return query(w << 1, L, mid, a, b);
        if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
        return min(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
    }
};

segtree segx, segy;
vi cx, cy;
pii arr[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;
        cx.PB(p.fi);
        cy.PB(p.se);
        arr[i] = p;
    }
    sort(ALL(cx)); cx.erase(unique(ALL(cx)), cx.end());
    sort(ALL(cy)); cy.erase(unique(ALL(cy)), cy.end());
    FOR(i, 0, M)
    {
        int x = indexof(arr[i].fi, cx), y = indexof(arr[i].se, cy);
        segx.pts[x].push({arr[i].se, i});
        segy.pts[y].push({arr[i].fi, i});
    }
    segx.build(1, 0, SZ(cx) - 1);
    segy.build(1, 0, SZ(cy) - 1);
    while(Q--)
    {
        // cerr << "TREE\n";
        int typ, idx;
        cin >> typ >> idx;
        // cerr << "QUERY " << typ << ' ' << idx << endl;
        if (typ == 1)
        {
            idx--;
            if (idx >= M) continue;
            // cerr << "idx = " << idx << endl;
            if (arr[idx] == MP(-1, -1))
            {
                get(V[idx]);
                pii p = V[idx] -> pos;
                cout << p.fi << ' ' << p.se << '\n';
            }
            else
            {
                cout << arr[idx].fi << ' ' << arr[idx].se << '\n';
            }
        }
        if (typ == 2)
        {
            //horizontal sweep.
            // cerr << "horizontal " << idx << endl;
            pnn p = split(root, idx + 1, true), p1 = split(p.se, N - idx + 1, false);
            // // inorder(p1.fi);
            if (p1.fi)
            {
                p1.fi -> lazy.fi = N - idx;
            }
            root = merge(p.fi, merge(p1.fi, p1.se));
            segy.walk(1, 0, SZ(cy) - 1, 0, indexof(idx, cy), N - idx);
            vi vec = segy.res; segy.res.clear();
            for (int x : vec)
            {
                if (arr[x] == MP(-1, -1)) continue;
                ins(N - idx, arr[x].se, x);
                arr[x] = MP(-1, -1);
            }
            // assert(segy.query(1, 0, SZ(cy) - 1, 0, indexof(idx, cy)) >= N - idx);
            //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 + 1, true), p1 = split(p.se, idx, 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));
            segx.walk(1, 0, SZ(cx) - 1, 0, indexof(idx, cx), N - idx);
            vi vec = segx.res; segx.res.clear();
            for (int x : vec)
            {
                if (arr[x] == MP(-1, -1)) continue;
                ins(arr[x].fi, N - idx, x);
                arr[x] = MP(-1, -1);
            }
            // assert(segx.query(1, 0, SZ(cx) - 1, 0, indexof(idx, cx)) >= N - idx);
        }
        if (typ == 4)
        {
            cin >> idx;
            continue;
        }
    }
    return 0;
}

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