Submission #740372

#	Time	Username	Problem	Language	Result	Execution time	Memory
740372		finn__	Sweeping (JOI20_sweeping)	C++17	0 / 100	594 ms	72116 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;

constexpr size_t M = 500000;

uint32_t compare_mode = 0;

struct segment
{
    int32_t i1, i2, x1, x2, y1, y2;

    bool operator<(segment const &s) const
    {
        return !compare_mode ? i1 < s.i1 : (compare_mode == 1 ? x1 < s.x1 : y1 > s.y1);
    }
};

set<segment> s;
pair<int32_t, int32_t> p[M];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int64_t n, m, q;
    cin >> n >> m >> q;
    for (int32_t i = 0; i < m; ++i)
    {
        cin >> p[i].first >> p[i].second;
        segment t = {i, i, p[i].first, p[i].first, p[i].second, p[i].second};
        if (!s.empty())
        {
            auto it = --s.end();
            if (it->x1 == it->x2 && it->x2 == p[i].first)
            {
                t.y2 = it->y2;
                t.i1 = it->i1;
                s.erase(it);
            }
            else if (it->y1 == it->y2 && it->y2 == p[i].second)
            {
                t.x1 = it->x1;
                t.i1 = it->i1;
                s.erase(it);
            }
        }
        s.insert(t);
    }

    while (q--)
    {
        size_t t;
        cin >> t;

        if (t == 1)
        {
            int32_t i;
            cin >> i, --i;
            compare_mode = 0;
            auto it = prev(s.upper_bound((segment){i, i, 0, 0, 0, 0}));
            cout << max(it->x1, p[i].first) << ' ' << max(it->y1, p[i].second) << '\n';
        }
        else if (t == 2)
        {
            int32_t l;
            cin >> l;
            compare_mode = 2;
            auto it = s.lower_bound((segment){0, 0, 0, 0, l, l});
            segment t = {INT32_MAX, -1, n - l, n - l, INT32_MAX, -1};
            while (it != s.end() && it->x1 <= n - l)
            {
                t.y1 = min(t.y1, it->y1);
                t.y2 = max(t.y2, it->y2);
                if (it->x2 <= n - l)
                {
                    t.i1 = min(t.i1, it->i1);
                    t.i2 = max(t.i2, it->i2);
                    it = s.erase(it);
                }
                else
                {
                    int32_t a = it->i1, b = it->i2;
                    while (a < b)
                    {
                        size_t const mid = (a + b + 1) / 2;
                        if (max(p[mid].first, it->x1) > n - l)
                            b = mid - 1;
                        else
                            a = mid;
                    }
                    t.i1 = min(t.i1, it->i1);
                    t.i2 = max(t.i2, a);
                    if (a != it->i2)
                    {
                        segment u = {a + 1, it->i2, max(p[a + 1].first, it->x1), it->x2, it->y1, it->y1};
                        s.erase(it);
                        s.insert(u);
                    }
                    else
                    {
                        s.erase(it);
                    }
                    break;
                }
            }
            if (t.i1 != INT32_MAX)
                s.insert(t);
        }
        else if (t == 3)
        {
            int32_t l;
            cin >> l;
            compare_mode = 1;
            auto it = s.upper_bound((segment){0, 0, l, l, 0, 0});
            if (it == s.begin())
                continue;
            --it;
            segment t = {INT32_MAX, -1, INT32_MAX, -1, n - l, n - l};
            while (it->y1 <= n - l)
            {
                t.x1 = min(t.x1, it->x1);
                t.x2 = max(t.x2, it->x2);
                if (t.y2 <= n - l)
                {
                    t.i1 = min(t.i1, it->i1);
                    t.i2 = max(t.i2, it->i2);
                    it = s.erase(it);
                    if (it == s.begin())
                        break;
                    --it;
                }
                else
                {
                    int32_t a = it->i1, b = it->i2;
                    while (a < b)
                    {
                        size_t const mid = (a + b) / 2;
                        if (max(p[mid].second, it->y1) <= n - l)
                            b = mid;
                        else
                            a = mid + 1;
                    }
                    t.i1 = min(t.i1, a);
                    t.i2 = max(t.i2, it->i2);
                    if (a != it->i1)
                    {
                        segment u = {it->i1, a - 1, it->x1, it->x1, max(it->y1, p[a - 1].second), it->y2};
                        s.erase(it);
                        s.insert(u);
                    }
                    else
                    {
                        s.erase(it);
                    }
                    break;
                }
            }
            if (t.i1 != INT32_MAX)
                s.insert(t);
        }
        else
        {
        }
    }
}

Compilation message (stderr)

sweeping.cpp: In function 'int main()':
sweeping.cpp:70:43: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
   70 |             segment t = {INT32_MAX, -1, n - l, n - l, INT32_MAX, -1};
      |                                         ~~^~~
sweeping.cpp:70:50: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
   70 |             segment t = {INT32_MAX, -1, n - l, n - l, INT32_MAX, -1};
      |                                                ~~^~~
sweeping.cpp:119:58: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
  119 |             segment t = {INT32_MAX, -1, INT32_MAX, -1, n - l, n - l};
      |                                                        ~~^~~
sweeping.cpp:119:65: warning: narrowing conversion of '(n - ((int64_t)l))' from 'int64_t' {aka 'long int'} to 'int32_t' {aka 'int'} [-Wnarrowing]
  119 |             segment t = {INT32_MAX, -1, INT32_MAX, -1, n - l, n - l};
      |                                                               ~~^~~

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