oj.uz

Submission #715718

# Submission time Handle Problem Language Result Execution time Memory
715718 2023-03-27T15:55:06 Z hamidh100 Furniture (JOI20_furniture) C++17
100 / 100
 891 ms 58288 KB 
/* In the name of God */

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <map>
#include <numeric>
#include <limits>
#include <limits.h>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <random>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef map<int, int> MPII;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define POP pop_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define Yes cout << "Yes\n"
#define YES cout << "YES\n"
#define No cout << "No\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld eps = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int mod_(int a){ int res = a + MOD; return (res >= MOD? res - MOD : res); }
inline int mod_add(int a, int b){ int res = a + b; return (res >= MOD? res - MOD : res); }
inline int mod_neg(int a, int b){ int res = (abs(a - b) < MOD? a - b : (a - b) % MOD); return (res < 0? res + MOD : res); }
inline int mod_mlt(int a, int b){ return (1ll * a * b % MOD); }
inline string intToString(ll a){ char x[100]; sprintf(x, "%lld", a); string s = x; return s; }
inline ll stringToInt(string s){ ll res; char x[100]; strcpy(x, s.c_str()); sscanf(x, "%lld", &res); return res; }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 1002;

int n, m, deg1[MAXN][MAXN], degn[MAXN][MAXN];
bool a[MAXN][MAXN];
set<PII> goodie[2 * MAXN];

void upd(int x, int y){
    queue<PII> q;
    if (deg1[x][y]){
        deg1[x][y] = 0;
        q.push({x, y});
    }
    while (!q.empty()){
        auto v = q.front();
        int xx = v.first, yy = v.second;
        q.pop();
        goodie[xx + yy].erase(MP(xx, yy));
        deg1[xx + 1][yy]--, deg1[xx][yy + 1]--;
        if (deg1[xx + 1][yy] == 0 && xx + 1 <= n) q.push({xx + 1, yy});
        if (deg1[xx][yy + 1] == 0 && yy + 1 <= m) q.push({xx, yy + 1});
    }

    if (degn[x][y]){
        degn[x][y] = 0;
        q.push({x, y});
    }
    while (!q.empty()){
        auto v = q.front();
        int xx = v.first, yy = v.second;
        q.pop();
        goodie[xx + yy].erase(MP(xx, yy));
        degn[xx - 1][yy]--, degn[xx][yy - 1]--;
        if (degn[xx - 1][yy] == 0 && xx - 1 >= 1) q.push({xx - 1, yy});
        if (degn[xx][yy - 1] == 0 && yy - 1 >= 1) q.push({xx, yy - 1});
    }

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            deg1[i][j] = degn[i][j] = 2;
            goodie[i + j].insert(MP(i, j));
        }
        deg1[i][1] = 1;
        degn[i][m] = 1;
    }
    fill(deg1[1], deg1[1] + m + 1, 1), fill(degn[n], degn[n] + m + 1, 1);

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
            if (a[i][j] == 1) upd(i, j);
        }
    }
    int q; cin >> q;
    while (q--){
        int x, y;
        cin >> x >> y;
        int sz = goodie[x + y].size();
        bool another = (sz > 1 || (sz == 1 && goodie[x + y].count(MP(x, y)) == 0));
        cout << another << endl;
        if (another) upd(x, y);
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 3 ms 1492 KB Output is correct
3 Correct 4 ms 1620 KB Output is correct
4 Correct 6 ms 1620 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 8 ms 1748 KB Output is correct
7 Correct 6 ms 1748 KB Output is correct
8 Correct 7 ms 1748 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 3 ms 1492 KB Output is correct
3 Correct 4 ms 1620 KB Output is correct
4 Correct 6 ms 1620 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 8 ms 1748 KB Output is correct
7 Correct 6 ms 1748 KB Output is correct
8 Correct 7 ms 1748 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct
10 Correct 18 ms 3540 KB Output is correct
11 Correct 6 ms 1364 KB Output is correct
12 Correct 728 ms 54104 KB Output is correct
13 Correct 358 ms 49768 KB Output is correct
14 Correct 891 ms 52092 KB Output is correct
15 Correct 882 ms 49980 KB Output is correct
16 Correct 688 ms 53724 KB Output is correct
17 Correct 768 ms 56616 KB Output is correct
18 Correct 840 ms 55176 KB Output is correct
19 Correct 697 ms 58288 KB Output is correct
20 Correct 633 ms 58256 KB Output is correct
21 Correct 767 ms 58188 KB Output is correct