Submission #1223517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223517		iulia_morariu	Paint (COI20_paint)	C++20	9 / 100	3098 ms	464012 KiB

paint

#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
// #include <bits/stdc++.h>
#define in  cin
#define out cout
#define mkp make_pair

using namespace std;

vector< vector<int> > v;
int ox[] = {0, 0, 1, -1};
int oy[] = {1, -1, 0, 0};

void fill(int x, int y, int c){
    int ini = v[x][y];

    if(ini == c) return;

    v[x][y] = c;
    queue< pair<int, int> > q;
    q.push( mkp(x, y) );
    while(!q.empty()){
        x = q.front().first; y = q.front().second; q.pop();
        v[x][y] = c;
        for(int i = 0; i < 4; i++){
            if(x + ox[i] < 0 || x + ox[i] >= v.size() || y + oy[i] < 0 || y + oy[i] >= v[x].size()) continue;
            if(v[x + ox[i]][y + oy[i]] == ini){
                q.push(mkp(x + ox[i], y + oy[i]));
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int n, m; in >> n >> m;

    if(n == 1){
        int l[m];
        for(int i = 0; i < m; i++) in >> l[i];
        set< pair<int, pair<int, int> > > s;

        int ls = 0;
        for(int i = 1; i < m; i++){
            if(l[i] != l[i - 1]){
                s.insert( mkp(ls, mkp(i - 1, l[i - 1])) );
                ls = i;
            }
        }
        s.insert( mkp(ls, mkp( m - 1, l[m - 1] )) );

        // cout << "s : ";
        // for(const auto &x : s){
        //     cout << "( " << x.first << " , " << x.second.first << " , " << x.second.second << " ) ";
        // }
        // cout << '\n';

        int q; in >> q;
        for(int ii = 0; ii < q; ii++){
            int x, y, c; in >> x >> y >> c; x--; y--;
            auto it = s.lower_bound(mkp( y, mkp(0, 0) ));
            if(it == s.end() || (*it).first > y) it--;
            if((*it).second.second == c) continue; // nu am ce modifica
            pair< int, pair<int, int> > nou = (*it);
            // cout << y << " e din intervalul " << nou.first << " , " << nou.second.first << " , " << nou.second.second << endl;
            nou.second.second = c;
            if( it != s.begin() ){
                auto i1 = it; i1--;
                if((*i1).second.second == nou.second.second){
                    // cout << "  -- > merge ( " << (*i1).first << " , " << (*i1).second.first << " ) cu mine" << endl;
                    nou.first = (*i1).first;
                    s.erase(i1);
                }
            }

            auto i1 = it; i1++;
            if(i1 != s.end() && (*i1).second.second == nou.second.second){
                // cout << "  -- > merge ( " << (*i1).first << " , " << (*i1).second.first << " ) cu mine" << endl;
                nou.second.first = (*i1).second.first;
                s.erase(i1);
            }
            s.erase(it);
            s.insert(nou);

            // cout << "s : ";
            // for(const auto &x : s){
            //     cout << "( " << x.first << " , " << x.second.first << " , " << x.second.second << " ) ";
            // }
            // cout << endl;
        }

        auto it = s.begin();
        for(int i = 0; i < m; i++){
            if(i > (*it).second.first) it++;
            out << (*it).second.second << " ";
        }

        return 0;
    }

    v.resize(n);
    for(int i = 0; i < n; i++) v[i].resize(m);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) in >> v[i][j];
    }
    int q; in >> q;
    if(n * m * q <= 100000000){
        for(int i = 0; i < q; i++){
            int x, y, c; in >> x >> y >> c;
            x--; y--;
            fill(x, y, c);
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++) out << v[i][j] << " ";
            out << '\n';
        }
        return 0;
    }

    return 0;
}

/*
1 9
0 0 1 1 1 0 0 2 3
3
1 3 0
1 8 3
1 9 2
*/

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