| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1292167 | jhwest2 | 웜뱃 (IOI13_wombats) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = (int)1e9 + 10;
struct Query {
int t, x, y, w;
} Q[200500];
int r, c, H[5000][200], V[5000][200], P[51][200][200];
// transition from row (x - 1) to row x
void transition(int x, int *S, int *D) {
fill(D, D + c, INF);
int sum = 0, mn = INF;
for (int i = 0; i < c; i++) {
sum += H[x][i];
mn = min(mn, S[i] - sum + V[x][i]);
D[i] = min(D[i], mn + sum);
}
sum = 0; mn = INF;
for (int i = c - 1; i >= 0; i--) {
D[i] = min(D[i], mn + sum);
mn = min(mn, S[i] - sum + V[x][i]);
sum += H[x][i];
}
}
void dnc(int x, int *S, int *D, int l, int r, int s, int e) {
if (l >= r) return;
if (s == e) {
for (int i = l; i < r; i++) {
D[i] = S[s] + P[x][s][i];
}
return;
}
int m = (l + r) / 2;
int mn = INF, p = -1;
for (int i = s; i <= e; i++) {
if (mn > S[i] + P[x][i][m]) {
mn = S[i] + P[x][i][m];
p = i;
}
}
D[m] = mn;
dnc(x, S, D, l, m, s, p);
dnc(x, S, D, m + 1, r, p, e);
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> r >> c;
for (int i = 0; i < r; i++) {
for (int j = 1; j < c; j++) {
cin >> H[i][j];
}
}
for (int i = 1; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> V[i][j];
}
}
int sz; cin >> sz;
for (int i = 0; i < sz; i++) {
int t; cin >> t;
if (t == 1){
int x, y, w;
cin >> x >> y >> w;
Q[i] = {t, x, y + 1, w};
}
else if (t == 2) {
int x, y, w;
cin >> x >> y >> w;
Q[i] = {t, x + 1, y, w};
}
else {
int x, y;
cin >> x >> y;
Q[i] = {t, x, y, 0};
}
}
const int BS = 50;
for (int ll = 0, rr = 0; ll < sz; ll = rr) {
int cnt_q = 0;
while (rr < sz && cnt_q + (Q[rr].t != 3) <= BS) {
cnt_q += Q[rr++].t != 3;
}
vector<int> pos;
pos.push_back(0);
pos.push_back(r - 1);
for (int i = ll; i < rr; i++) {
if (Q[i].t != 3) pos.push_back(Q[i].x);
}
sort(pos.begin(), pos.end());
pos.erase(unique(pos.begin(), pos.end()), pos.end());
for (int i = 0; i < (int)pos.size() - 1; i++) {
for (int j = 0; j < c; j++) {
int S[c], D[c];
fill(S, S + c, INF);
S[j] = 0;
for (int k = pos[i] + 1; k < pos[i + 1]; k++) {
transition(k, S, D);
for (int l = 0; l < c; l++) S[l] = D[l];
}
for (int k = 0; k < c; k++) P[i][j][k] = S[k];
}
}
for (int i = ll; i < rr; i++) {
if (Q[i].t == 1) {
H[Q[i].x][Q[i].y] = Q[i].w;
}
else if (Q[i].t == 2) {
V[Q[i].x][Q[i].y] = Q[i].w;
}
else {
int S[c], D[c];
fill(S, S + c, INF);
S[Q[i].x] = 0;
transition(0, S, D);
for (int j = 0; j < c; j++) S[j] = D[j];
for (int i = 0; i < (int)pos.size() - 1; i++) {
dnc(i, S, D, 0, c, 0, c - 1);
transition(pos[i + 1], D, S);
}
cout << S[Q[i].y] << '\n';
}
}
}
}