oj.uz

Submission #383716

# Submission time Handle Problem Language Result Execution time Memory
383716 2021-03-30T16:11:07 Z VodkaInTheJar Sweeping (JOI20_sweeping) C++14
12 / 100
 18000 ms 100812 KB 
#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 split1(node *t, pair <int, int> x, node *&l, node *&r)
{
    push(t);
    if (!t)
    {
        l = r = nullptr;
        return;
    }

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

    else 
    split1(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;
    split1(r, make_pair(l->x, l->y - rand() % 2), ll, rr);

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

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

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

void print(node *x)
{
    if (!x)
        return;

    cout << "left" << endl;
    print(x->l);
    cout << x->x << " " << x->y << endl;
    cout << "right";
    print(x->r);
}

struct treap
{
    node *group;
    int prior; 
    int x, y, min_y;
    treap *l, *r; 

    treap() {}
    treap(node *t)
    {
        group = t; 
        pair <int, int> curr = leftmost(t);
        
        prior = random_generator();
        x = curr.first;
        y = min_y = curr.second;

        l = r = nullptr; 
    }
};

void pull_treap(treap *t)
{
    t->min_y = t->y;
    if (t->l)
    t->min_y = min(t->min_y, t->l->min_y);

    if (t->r)
        t->min_y = min(t->min_y, t->r->min_y);
}

void merge(treap *l, treap *r, treap *&t)
{
    if (!l || !r)
    {
        t = l ? l : r; 
        return;
    }

    if (l->prior > r->prior)
        merge(l->r, r, l->r), t = l;

    else 
        merge(l, r->l, r->l), t = r;

    pull_treap(t);
}

void split_treap(treap *t, int x, treap *&l, treap *&r)
{
    if (!t)
    {
        l = r = nullptr;
        return;
    }

    if (x < t->x)
        split_treap(t->l, x, l, t->l), r = t; 

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

    pull_treap(t);
}

void insert(treap *&t, treap *x)
{
    treap *l, *r;
    split_treap(t, x->x - rand() % 2, l, r);
    merge(l, x, l);
    merge(l, r, t);
}

const int maxm = 500003;

node *where[maxm * 3];
treap *root = nullptr;

int n, m, q;
void read()
{
   // node *tt = nullptr;
  //  merge_op(tt, new node(3, 4), tt);
  //  merge_op(tt, new node(3, 4), tt);
   // merge_op(tt, new node(3 ,4), tt);
   // merge_op(tt, new node(3, 4), tt);
   // merge_op(tt, new node(3, 4), tt);

   // print(tt);
   // return;
    
	cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;

        where[i] = new node(x, y);
        insert(root, new treap(where[i]));
    }
}

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};
}


vector <treap*> to_add;
node *all;
void clean1(treap *&x, int pos)
{
    if (!x)
        return;

    if (x->min_y > pos)
        return;

    clean1(x->l, pos);
    clean1(x->r, pos);

    if (x->y <= pos)
    {
        node *l, *r;
        split(x->group, {n-pos, pos}, l, r);

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

        merge_op(all, l, all);
        if (r)
        to_add.push_back(new treap(r));

        merge(x->l, x->r, x);
    }
}

void clean2(treap *&x, int pos)
{
    if (!x)
        return;

    if (x->min_y > n-pos)
        return;

    clean2(x->l, pos);
    clean2(x->r, pos);

    if (x->y <= n-pos)
    {
        node *l, *r;
        split(x->group, {pos, n-pos}, l, r);

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

        merge_op(all, l, all);
        if (r)
        to_add.push_back(new treap(r));

        merge(x->l, x->r, x);
    }
}

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;

                all = nullptr;
                to_add.clear();

                treap *l, *r;
                split_treap(root, n-x, l, r);

                clean1(l, x);
                merge(l, r, root);

                if (all)
                insert(root, new treap(all));
                for (auto i: to_add)
                    insert(root, i);
            }

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

                all = nullptr;
                to_add.clear();

                treap *l, *r;
                split_treap(root, x, l, r);

                clean2(l, x);
                merge(l, r, root);

                if (all)
                insert(root, new treap(all));
                for (auto i: to_add)
                    insert(root, i);
            }

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

            where[curr_idx] = new node(x, y);
            insert(root, new treap(where[curr_idx]));
            curr_idx++;
        }
    }
}

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 876 KB Output is correct
2 Correct 7 ms 620 KB Output is correct
3 Correct 5 ms 876 KB Output is correct
4 Correct 8 ms 876 KB Output is correct
5 Correct 12 ms 1132 KB Output is correct
6 Correct 5 ms 620 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 18065 ms 59752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1868 ms 76524 KB Output is correct
2 Correct 1570 ms 70728 KB Output is correct
3 Correct 1133 ms 77228 KB Output is correct
4 Correct 2354 ms 100812 KB Output is correct
5 Correct 1705 ms 72648 KB Output is correct
6 Correct 1539 ms 69692 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1868 ms 76524 KB Output is correct
2 Correct 1570 ms 70728 KB Output is correct
3 Correct 1133 ms 77228 KB Output is correct
4 Correct 2354 ms 100812 KB Output is correct
5 Correct 1705 ms 72648 KB Output is correct
6 Correct 1539 ms 69692 KB Output is correct
7 Execution timed out 18030 ms 59560 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 876 KB Output is correct
2 Correct 7 ms 620 KB Output is correct
3 Correct 5 ms 876 KB Output is correct
4 Correct 8 ms 876 KB Output is correct
5 Correct 12 ms 1132 KB Output is correct
6 Correct 5 ms 620 KB Output is correct
7 Execution timed out 18065 ms 59752 KB Time limit exceeded
8 Halted 0 ms 0 KB -