Submission #854970

#	Time	Username	Problem	Language	Result	Execution time	Memory
854970		vjudge1	Paint (COI20_paint)	C++17	8 / 100	345 ms	5396 KiB

paint

#define taskname ""
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifndef LOCAL
#define cerr \
    if (0)   \
    cerr
#endif

const bool multitest = 0;
// Subtask 1: Simple Query DFS
int r, s, q;
vector<vector<int>> a;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
const int oo = 1e9;

class Subtask1
{
public:
    void DFS(int x, int y, int color, int precolor)
    {
        if ((!(x >= 1 && x <= r && y >= 1 && y <= s)) || (a[x][y] != precolor))
            return;
        a[x][y] = color;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            DFS(nx, ny, color, precolor);
        }
    }
} st1solve;

class Subtask2
{
public:
    struct TRange
    {
        int l, r, v;

        bool operator<(const TRange &o) const
        {
            return l < o.l;
        }
    };
    set<TRange> ranges;
    void makerange()
    {
        int len = 1, st = 1;
        for (int i = 2; i <= s; i++)
        {
            if (a[1][i] == a[1][i - 1])
                len++;
            else
            {
                ranges.insert({st, st + len - 1, a[1][i - 1]});
                st = i;
                len = 1;
            }
        }
        ranges.insert({st, st + len - 1, a[1][s]});
    }
    void recolor(int pos, int c)
    {
        auto it = ranges.lower_bound({pos, -oo, -oo});
        auto val = *it;
        if (!(val.l <= pos && pos <= val.r))
        {
            it--;
            val = *it;
        }
        cerr << "Current Changing Range: "
             << "[" << val.l << ", " << val.r << "]"
             << " - Color: " << val.v << '\n';
        int prevcolor = val.v;
        if (val.v == c)
            return;
        val.v = c;
        auto forwardit = next(it);
        auto backit = prev(it);
        ranges.erase(it);
        while (forwardit->v == prevcolor)
        {
            auto nex = next(forwardit);
            val.r = max(val.r, forwardit->r);
            ranges.erase(forwardit);
            forwardit = nex;
        }
        while (backit->v == prevcolor)
        {
            auto nex = prev(backit);
            val.l = min(val.l, forwardit->l);
            ranges.erase(backit);
            backit = nex;
        }
        ranges.insert(val);
    }
} st2solve;

void sub1()
{
    while (q--)
    {
        int ix, iy, c;
        cin >> ix >> iy >> c;
        if (c == a[ix][iy])
            continue;
        st1solve.DFS(ix, iy, c, a[ix][iy]);
    }
}

void sub2()
{
    st2solve.makerange();
    for (auto val : st2solve.ranges)
    {
        cerr << "[l, r]"
             << "[" << val.l << ", " << val.r << "], col: " << val.v << '\n';
    }
    while (q--)
    {
        int t, pos, c;
        cin >> t >> pos >> c;
        st2solve.recolor(pos, c);
    }
}

void solve()
{
    // Input
    cin >> r >> s;
    a.assign(r + 3, vector<int>(s + 3));
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= s; j++)
            cin >> a[i][j];
    cin >> q;

    if (r != 1 && r * s <= 1e4 && q <= 1e4)
    {
        sub1();
        for (int i = 1; i <= r; i++, cout << '\n')
            for (int j = 1; j <= s; j++)
                cout << a[i][j] << ' ';
    }
    else if (r == 1)
    {
        sub2();
        vector<int> ans(s + 3);
        for (auto [l, r, col] : st2solve.ranges)
        {
            for (int i = l; i <= r; i++)
            {
                ans[i] = col;
            }
        }
        for (int i = 1; i <= s; i++)
            cout << ans[i] << ' ';
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(taskname ".inp", "r"))
    {
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }
    int tc = 1;
    if (multitest)
        cin >> tc;
    while (tc--)
    {
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

paint.cpp: In function 'int32_t main()':
paint.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         freopen(taskname ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen(taskname ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52