Submission #383605

#	Time	Username	Problem	Language	Result	Execution time	Memory
383605		VodkaInTheJar	Sweeping (JOI20_sweeping)	C++14	0 / 100	18024 ms	2097156 KiB

sweeping

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;
mt19937 random_generator(chrono::steady_clock::now().time_since_epoch().count());

struct node
{
    int x, y;
    int lazy_x, lazy_y; 
    int prior; 
    node *l, *r, *par;

    node() {}
    node(int _x, int _y)
    {
        x = _x; 
        y = _y;
        lazy_x = lazy_y = -1; 
        prior = random_generator();
        l = r = par = nullptr;
    }
};

void push(node *t)
{
    if (!t)
        return;

    if (t->lazy_x != -1)
    {
        t->x = t->lazy_x;
        if (t->l)
            t->l->lazy_x = t->lazy_x;

        if (t->r)
            t->r->lazy_x = t->lazy_x;
        
        t->lazy_x = -1; 
    }

    if (t->lazy_y != -1)
    {
        t->y = t->lazy_y;
        if (t->l)
            t->l->lazy_y = t->lazy_y;

        if (t->r) 
            t->r->lazy_y = t->lazy_y;

        t->lazy_y = -1; 
    }
}

void pull(node *t)
{
    if (!t)
        return;

    t->par = nullptr;
    if (t->l)
        t->l->par = t;

    if (t->r)
        t->r->par = t; 
}

void split(node *t, pair <int, int> x, node *&l, node *&r)
{
    push(t);
    if (!t)
    {
        l = r = nullptr;
        return;
    }

    if (t->x > x.first || t->y > x.second)
        split(t->l, x, l, t->l), r = t;

    else 
        split(t->r, x, t->r, r), l = t;

    pull(t);
}

void merge_op(node *l, node *r, node *&t)
{
    push(l);
    push(r);

    if (!l || !r)
    {
        t = l ? l : r;
        return;
    }

    if (l->prior < r->prior)
        swap(l, r);

    node *ll, *rr;
    split(r, make_pair(l->x, l->y), ll, rr);

    merge_op(l->l, ll, l->l);
    merge_op(l->r, rr, l->r);
    t = l;
    pull(t);
}

struct segtree
{
    set <node*> s;
    segtree *l, *r;

    segtree() {s.clear(), l = r = nullptr;}
};

void range_update(segtree *tr, int l, int r, int ll, int rr, node *&to_add)
{
    if (l > rr || r < ll)
        return;

    if (l >= ll && r <= rr)
    {
        tr->s.insert(to_add);
        return;
    }

    int mid = (l + r) / 2;
    if (!tr->l)
        tr->l = new segtree();

    if (!tr->r)
        tr->r = new segtree();

    range_update(tr->l, l, mid, ll, rr, to_add);
    range_update(tr->r, mid + 1, r, ll, rr, to_add);
}

void remove(segtree *tr, int l, int r, int ll, int rr, node *&to_remove)
{
    if (l > rr || r < ll)
        return;

    if (l >= ll && r <= rr)
    {
        tr->s.erase(to_remove);
        return;
    }

    int mid = (l + r) / 2;

    if (tr->l)
    remove(tr->l, l, mid, ll, rr, to_remove);
    
    if (tr->r)
    remove(tr->r, mid + 1, r, ll, rr, to_remove);
}

pair <int, int> leftmost(node *t)
{
    push(t);
    if (t->l)
        return leftmost(t->l);

    return {t->x, t->y};
}

const int maxm = 500003;

node *where[maxm * 3];
segtree *tr1 = new segtree(), *tr2 = new segtree();

int n, m, q;
vector <node*> roots;
void read()
{
	cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;

        where[i] = new node(x, y);
        range_update(tr1, 0, n, y, n-x, where[i]);
        range_update(tr2, 0, n, x, n-y, where[i]);
    }
}

void change1(segtree *tr, int l, int r, int pos, node *&to_add)
{
    vector <node*> vec(tr->s.begin(), tr->s.end());
    for (auto i: vec)
    {
        pair <int, int> curr = leftmost(i);
      
        /*
        if (curr.second < pos || curr.first > n-pos)
        {
            cout << pos << endl;
            exit(0);
        }
        assert(curr.second >= pos && curr.first <= n-pos);
        */

        remove(tr1, 0, n, curr.second, n - curr.first, i);
        remove(tr2, 0, n, curr.first, n - curr.second, i);

        node *l, *r;
        split(i, {n-pos, pos}, l, r);

        if (r)
        {
            curr = leftmost(r);
            range_update(tr2, 0, n, curr.second, n - curr.first, r);
            range_update(tr2, 0, n, curr.first, n - curr.second, r);
        }

        if (l)
            l->lazy_x = n-pos;
       
        merge_op(to_add, l, to_add);
    }

    if (l == r)
        return;

    int mid = (l + r) / 2;
    if (tr->l && pos <= mid)
        change1(tr->l, l, mid, pos, to_add);

    if (tr->r && pos > mid)
        change1(tr->r, mid + 1, r, pos, to_add);
}

void change2(segtree *tr, int l, int r, int pos, node *&to_add)
{
    vector <node*> vec(tr->s.begin(), tr->s.end());
    for (auto i: vec)
    {
        pair <int, int> curr = leftmost(i);

        /*
        if (curr.first > pos || curr.second > n-pos)
        {
            assert(i == where[1]);
            cout << pos << " " << l << " " << r << " " << curr.first << " " << curr.second << endl; 
            exit(0);
        }
        assert(curr.first >= pos && curr.second <= n-pos);

        */

        remove(tr1, 0, n, curr.second, n - curr.first, i);
        remove(tr2, 0, n, curr.first, n - curr.second, i);

        node *l, *r;
        split(i, {pos, n-pos}, l, r);

        if (r)
        {
            curr = leftmost(r);
            range_update(tr1, 0, n, curr.second, n - curr.first, r);
            range_update(tr2, 0, n, curr.first, n - curr.second, r);
        }

        if (l)
            l->lazy_y = n-pos;

        merge_op(to_add, l, to_add);
    }

    if (l == r)
        return;

    int mid = (l + r) / 2;
    if (tr->l && pos <= mid)
        change2(tr->l, l, mid, pos, to_add);

    if (tr->r && pos > mid)
        change2(tr->r, mid + 1, r, pos, to_add);
}

pair <int, int> get(node *t)
{
    int lazy_x = t->x, lazy_y = t->y;
    while (t)
    {
        if (t->lazy_x != -1)
            lazy_x = t->lazy_x;

        if (t->lazy_y != -1)
            lazy_y = t->lazy_y;

        t = t->par;
    }

    return {lazy_x, lazy_y};
}

void solve()
{
	int curr_idx = m + 1;
    while (q--)
    {
        int type;
        cin >> type;

        if (type == 1)
        {
            int idx;
            cin >> idx;

            auto ans = get(where[idx]);
            cout << ans.first << " " << ans.second << endl;
        }

        else
            if (type == 2)
            {
                int x;
                cin >> x;

                node *to_add = nullptr;
                change1(tr1, 0, n, x, to_add);
               
                if (!to_add)
                    continue;

                auto curr = leftmost(to_add);
                range_update(tr1, 0, n, curr.second, n-curr.first, to_add);
                range_update(tr2, 0, n, curr.first, n-curr.second, to_add);
            }

        else 
            if (type == 3)
            {
                int x;
                cin >> x;

                node *to_add = nullptr;
                change2(tr2, 0, n, x, to_add);

                if (!to_add)
                    continue;

                auto curr = leftmost(to_add);
                range_update(tr1, 0, n, curr.second, n-curr.first, to_add);
                range_update(tr2, 0, n, curr.first, n-curr.second, to_add);
            }

        else 
        {
            int x, y;
            cin >> x >> y;

            where[curr_idx] = new node(x, y);
            range_update(tr1, 0, n, y, n-x, where[curr_idx]);
            range_update(tr2, 0, n, x, n-y, where[curr_idx]);

            curr_idx++;
        }
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	read();
	solve();
}

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