Submission #521689

#	Time	Username	Problem	Language	Result	Execution time	Memory
521689		ivan24	Furniture (JOI20_furniture)	C++14	100 / 100	1779 ms	20012 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define F first
#define S second

ll min(ll x, ll y){
    return ((x < y) ? x : y);
}

ll max(ll x, ll y){
    return ((x > y) ? x : y);
}

class Grid{
private:
    ll w,h;
    vvi c;
    vii upper_path; // minimize y value
    vii left_path; // minimize x value
    bool check (ll x, ll y){
        return (h > x && x >= 0 && w > y && y >= 0);
    }
    bool check (ii p){
        return (h > p.F && p.F >= 0 && w > p.S && p.S >= 0);
    }
    void modify_path(ll x, ll y, vii& path, ll dx, ll dy){
        while (c[path[x+y].F][path[x+y].S] == 1){
            path[x+y].F += dx;
            path[x+y].S += dy;
        }
        ll bdx = max(dx,0), sdx = min(dx,0);
        ll bdy = max(dy,0), sdy = min(dy,0);
        vii for_mod;
        for (ll i = x+y-1; i >= 0; i--){
            ll diff = abs(path[i+1].F-path[i].F) + abs(path[i+1].S-path[i].S);
            //cout << "diff: " << diff << endl;
            if (diff == 1) break;
            ii cd = path[i+1];
            cd.F -= bdx; cd.S -= bdy;
            //cout << cd.F << " " << cd.S << endl;
            if (c[cd.F][cd.S] == 1) for_mod.push_back(cd);
            path[i] = cd;
        }
        for (ll i = x+y+1; w+h-2 >= i; i++){
            ll diff = abs(path[i-1].F-path[i].F) + abs(path[i-1].S-path[i].S);
            //cout << "diff: " << diff << endl;
            if (diff == 1) break;
            ii cd = path[i-1];
            cd.F -= sdx; cd.S -= sdy;
            //cout << cd.F << " " << cd.S << endl;
            if (c[cd.F][cd.S] == 1) for_mod.push_back(cd);
            path[i] = cd;
        }
        //cout << "reached\n";
        for (auto i: for_mod){
            add(i.F,i.S);
        }
    }
public:
    Grid(ll _h, ll _w){
        w = _w; h = _h;
        c.assign(h,vi(w,0));
        upper_path.resize(w+h-1);
        left_path.resize(w+h-1);
        for (ll i = 0; w+h-1 > i; i++){
            upper_path[i] = ii(max(0,i-w+1),min(i,w-1));
            left_path[i] = ii(min(i,h-1),max(0,i-h+1));
        }
    }
    ll add (ll x, ll y){
        //cout << "called: " << x << " " << y << endl;
        if (left_path[x+y] == ii(x,y) && upper_path[x+y] == ii(x,y)) return 0;
        c[x][y] = 1;
        if (upper_path[x+y] == ii(x,y)) modify_path(x,y,upper_path, 1, -1);
        if (left_path[x+y] == ii(x,y)) modify_path(x,y,left_path, -1, 1);
        return 1;
    }
    void print(){
        cout << "upper_path: \n";
        for (auto i: upper_path){
            cout << "(" << i.F << " , " << i.S << ") -> ";
        }
        cout << endl;
        cout << "left_path:\n";
        for (auto i: left_path){
            cout << "(" << i.F << " , " << i.S << ") -> ";
        }
        cout << endl;
        cout << "c:\n";
        for (ll i = 0; h > i; i++){
            for (ll j = 0; w > j; j++){
                if (upper_path[i+j] == ii(i,j) || left_path[i+j] == ii(i,j)) cout << "* ";
                else cout << c[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
};

int main(){
    ll h,w;
    cin >> h >> w;
    Grid grid(h,w);
    //grid.print();
    for (ll i = 0; h > i; i++){
        for (ll j = 0; w > j; j++){
            ll x; cin >> x;
            //cout << "added: " << i << " " << j << endl;
            if (x) grid.add(i,j);
        }
    }
    ll q; cin >> q;
    //grid.print();
    while (q--){
        ll x, y; cin >> x >> y;
        x--; y--;
        cout << grid.add(x,y) << '\n';
        //grid.print();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95