Submission #877590

#	Time	Username	Problem	Language	Result	Execution time	Memory
877590		danikoynov	Sweeping (JOI20_sweeping)	C++14	10 / 100	2302 ms	267136 KiB

sweeping

#include<bits/stdc++.h>

using namespace std;

const int maxm = 2 * 1500100;
const int maxq = 2 * 1000100;
struct dust
{
    int x, y, idx;

}d[maxm];

bool cmp_y(dust d1, dust d2)
{
    return d1.y < d2.y;
}

struct query
{
    int t, p, l, a, b, idx;


}task[maxq];

int n, m, q;
void input()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i ++)
    {
        cin >> d[i].x >> d[i].y;
        d[i].idx = i;
    }
    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].t;
        if (task[i].t == 1)
            cin >> task[i].p;
        else
        if (task[i].t == 2 || task[i].t == 3)
            cin >> task[i].l;
        else
        {
            cin >> task[i].a >> task[i].b;
            d[++ m].idx = m;
            task[i].idx = m;
            d[m].x = task[i].a;
            d[m].y = task[i].b;
        }
    }
}

void solve_slow()
{
    for (int i = 1; i <= q; i ++)
    {
        if (task[i].t == 1)
        {
            cout << d[task[i].p].x << " " << d[task[i].p].y << endl;
        }
        else
        if (task[i].t == 2)
        {
            for (int j = 1; j <= m; j ++)
            {
                if (d[j].x < n - task[i].l && d[j].y <= task[i].l)
                    d[j].x = n - task[i].l;
            }
        }
        else
        if (task[i].t == 3)
        {
            for (int j = 1; j <= m; j ++)
            {
                if (d[j].x <= task[i].l && d[j].y < n - task[i].l)
                    d[j].y = n - task[i].l;
            }
        }
        else
        {
            d[task[i].idx].x = task[i].a;
            d[task[i].idx].y = task[i].b;
        }
    }
}

const int inf = 1e9 + 10;

struct node
{
    int min_num, sec_num;

    node(int _min_num = inf, int _sec_num = inf)
    {
        min_num = _min_num;
        sec_num = _sec_num;
    }
};

node merge_node(node lf, node rf)
{
    node mf = lf;
    if (rf.min_num < mf.min_num)
    {
        mf.sec_num = mf.min_num;
        mf.min_num = rf.min_num;
    }
    else
    if (rf.min_num < mf.sec_num && rf.min_num != mf.min_num)
    {
        mf.sec_num = rf.min_num;
    }

    if (rf.sec_num < mf.min_num)
    {
        mf.sec_num = mf.min_num;
        mf.min_num = rf.sec_num;
    }
    else
    if (rf.sec_num < mf.sec_num && rf.sec_num != mf.min_num)
    {
        mf.sec_num = rf.sec_num;
    }

    return mf;
};


int lazy[4 * maxm];
node tree[4 * maxm];

void push_lazy(int root, int left, int right)
{
    if (lazy[root] == 0)
        return;

    if (tree[root].min_num < lazy[root])
        tree[root].min_num = lazy[root];
    ///cout << "push lazy " << root << " " << left << " " << right << " " << lazy[root] << endl;
    if (left != right)
    {
        lazy[root * 2] = max(lazy[root * 2], lazy[root]);
        lazy[root * 2 + 1] = max(lazy[root * 2 + 1], lazy[root]);
    }

    lazy[root] = 0;
}

void update_range(int root, int left, int right, int qleft, int qright, int val)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft && tree[root].min_num >= val)
        return;

    if (left >= qleft && right <= qright && tree[root].sec_num > val)
    {
        //cout << "update node " << left << " " << right << " " << tree[root].min_num << " " << tree[root].sec_num << endl;
        lazy[root] = val;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    update_range(root * 2, left, mid, qleft, qright, val);
    update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
    ///cout << "tree " << root << " " << left << " " << right << " " << tree[root].min_num << " " << tree[root].sec_num << endl;
}

void update_point(int root, int left, int right, int pos, int val)
{
    push_lazy(root, left, right);
    if (left == right)
    {
        tree[root].min_num = val;
        tree[root].sec_num = inf;
        return;
    }

    int mid = (left + right) / 2;
    if (pos <= mid)
        update_point(root * 2, left, mid, pos, val);
    else
        update_point(root * 2 + 1, mid + 1, right, pos, val);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}


int query(int root, int left, int right, int pos)
{
    push_lazy(root, left, right);
    if (left == right)
    {
        //cout << "query " << left << " " << right << " " << tree[root].min_num << endl;
        return tree[root].min_num;
    }

    int mid = (left + right) / 2;
    if (pos <= mid)
        return query(root * 2, left, mid, pos);

    return query(root * 2 + 1, mid + 1, right, pos);
}

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].min_num = d[left].x;
        tree[root].sec_num = inf;
            //cout << "tree " << root << " " << left << " " << right << " " << tree[root].min_num << " " << tree[root].sec_num << endl;
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
    ///cout << "tree " << root << " " << left << " " << right << " " << tree[root].min_num << " " << tree[root].sec_num << endl;
}

int rev[maxm];
void solve_second()
{
    sort(d + 1, d + m + 1, cmp_y);
    for (int i = 1; i <= m; i ++)
        rev[d[i].idx] = i;

    build_tree(1, 1, m);

    for (int i = 1; i <= q; i ++)
    {

        if (task[i].t == 1)
        {
            task[i].p = rev[task[i].p];

            cout << query(1, 1, m, task[i].p) << " " << d[task[i].p].y << endl;
        }
        else
        if (task[i].t == 2)
        {
            int lf = 1, rf = m;
            while(lf <= rf)
            {
                int mf = (lf + rf) / 2;
                if (d[mf].y <= task[i].l)
                    lf = mf + 1;
                else
                    rf = mf - 1;
            }

            update_range(1, 1, m, 1, rf, n - task[i].l);
        }
        else
        if (task[i].t == 3)
        {
            assert(false);
        }
        else
        if (task[i].t == 4)
        {
            task[i].idx = rev[task[i].idx];
            update_point(1, 1, m, task[i].idx, task[i].a);
        }
    }
}
void solve()
{
    input();
    ///cout << "----------" << endl;
    //if (m <= 7000 && q <= 5000)
      //  solve_slow();
    //else
        solve_second();
}

int main()
{
    solve();
    return 0;
}

Compilation message (stderr)

sweeping.cpp: In function 'void input()':
sweeping.cpp:45:15: warning: operation on 'm' may be undefined [-Wsequence-point]
   45 |             d[++ m].idx = m;
      |               ^~~~
sweeping.cpp:45:15: warning: operation on 'm' may be undefined [-Wsequence-point]
sweeping.cpp: In function 'void update_range(int, int, int, int, int, int)':
sweeping.cpp:152:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  152 |     if (left > qright || right < qleft && tree[root].min_num >= val)
      |                          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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