Submission #60341469

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 2e5 + 7;
const double PI = acos(-1), eps = 1e-7;
int h, w, n;
int ans[maxn];
void solve() {
    cin >> h >> w >> n;
    vector<vector<pair<int, int>>> a(h + 5, vector<pair<int, int>>(w + 5));
    vector<vector<int>>d(h + 5 ,vector<int>(w + 5));
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            a[i][j] = {0, 0};
            d[i][j] = h + 1;
        }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 2e5 + 7;
const double PI = acos(-1), eps = 1e-7;

int h, w, n;
int ans[maxn];

void solve() {
    cin >> h >> w >> n;
    vector<vector<pair<int, int>>> a(h + 5, vector<pair<int, int>>(w + 5));
    vector<vector<int>>d(h + 5 ,vector<int>(w + 5));
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            a[i][j] = {0, 0};
            d[i][j] = h + 1;
        }
    }
    int x, y, z;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y >> z;
        ans[i] = x;
        a[x][y] = {z, i};
    }
    for (int i = h; i >= 1; i--) {
        for (int j = 1; j <= w; j++) {
            if (a[i][j] != pair<int, int>{0, 0}) {
                int z = h + 1;
                for (int k = j; k <= min(w, j + a[i][j].first - 1); k++) {
                    z = min(z, d[i][k]);
                }
                ans[a[i][j].second] = z - 1;
                for (int k = j; k <= min(w, j + a[i][j].first - 1); k++) {
                    d[i - 1][k] = z - 1;
                }
                j = j + a[i][j].first - 1;
            } else {
                d[i - 1][j] = d[i][j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}


/*


 */

Submission Info

Judge Result