#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;
const int MAXN = 100100*10;
const ll MOD = 998244353;
const ll INF = 1e16;
const int MAXM = 770;
string info[MAXM][MAXM];
typedef array<int,3> Bee;
const int MAXSZ = MAXM*MAXM*10;
vector<map<Bee, int> > mp;
vector<map<Bee, Bee> > dp;
vector<map<Bee, Bee> > w[4];
int sz=0;
int res[MAXM][MAXM];
void dnc(int sx, int ex, int sy, int ey, int t) {
// cout<<sx<<bl<<ex<<bl<<sy<<bl<<ey<<" mp : "<<endl;
// for(auto [x,cnt] : mp[t]) {
// cout<<x[0]<<bl<<x[1]<<bl<<x[2]<<bl<<cnt<<endl;
// }
if(sx==ex || sy==ey) {
for(auto [x,cnt] : mp[t]) {
dp[t][x] = x;
} return;
}
if(sx+1==ex && sy+1==ey) {
for(auto [x,cnt] : mp[t]) {
int idx;
if(x[0]==3) idx=0;
else if(x[0]==2 && x[1]==1) idx=1;
else if(x[0]==2) idx=2;
else if(x[0]==1 && x[1]==2) idx=4;
else if(x[0]==1 && x[2]==2) idx=8;
else if(x[0]==1) idx=5;
else if(x[1]==3) idx=13;
else if(x[1]==2) idx=14;
else if(x[1]==1) idx=17;
else idx=26;
int col;
if(info[ex][ey][idx] == 'L') col=idx/9;
else if(info[ex][ey][idx] == 'D') col=idx/3%3;
else col=idx%3;
res[ex][ey] += col*cnt;
dp[t][x][col]++;
dp[t][x][idx/9]++;
dp[t][x][idx%3]++;
}
// cout<<sx<<bl<<ex<<bl<<sy<<bl<<ey<<" dp : "<<endl;
// for(auto [x,y] : dp[sz]) {
// cout<<x.a<<bl<<x.b<<bl<<x.c<<bl<<y.a<<bl<<y.b<<bl<<y.c<<endl;
// }
return;
}
map<Bee, int> bint; map<Bee, Bee> bbee;
int mx=sx+ex>>1, my=sy+ey>>1;
mp.push_back(bint); dp.push_back(bbee);
for(int j=0; j<4; j++) w[j].push_back(bbee);
for(auto [x, cnt] : mp[t]) {
int tot = mx-sx+my-sy+1;
int a = min(tot, max(0, x[0]-(ex-mx)));
int c = min(tot, max(0, x[2]-(ey-my)));
int b = tot-a-c;
mp[sz][{a,b,c}] += cnt;
w[0][t][x] = {a,b,c};
} int mx1 = sz++;
dnc(sx, mx, sy, my, mx1);
mp.push_back(bint); dp.push_back(bbee);
for(int j=0; j<4; j++) w[j].push_back(bbee);
for(auto [x, cnt] : mp[t]) {//if(sx==0&&mx==0&&my==2&&ey==3)cout<<"YEE"<<endl;
int tot1 = mx-sx+1, tot2 = ey-my;
int a = min(tot1, max(0, dp[mx1][w[0][t][x]][0]-(my-sy))) + min(tot2, max(0, x[0]-(ex-sx+my-sy+1)));
int c = min(tot1, dp[mx1][w[0][t][x]][2]) + min(tot2, x[2]);
int b = tot1+tot2-a-c;
mp[sz][{a,b,c}] += cnt;
w[1][t][x] = {a,b,c};
} int mx2 = sz++;
dnc(sx, mx, my, ey, mx2);
mp.push_back(bint); dp.push_back(bbee);
for(int j=0; j<4; j++) w[j].push_back(bbee);
for(auto [x, cnt] : mp[t]) {//if(mx+1==2&&ex==2&&sy==3&&my==3)cout<<"Yee"<<dp[mx1][w[t][0][x]].c<<endl;
int tot1 = ex-mx, tot2 = my-sy+1;
int a = min(tot1, x[0]) + min(tot2, dp[mx1][w[0][t][x]][0]);
int c = min(tot1, max(0, x[2]-(ey-sy+mx-sx+1))) + min(tot2, max(0, dp[mx1][w[0][t][x]][2]-(mx-sx)));
int b = tot1+tot2-a-c;
mp[sz][{a,b,c}] += cnt;
w[2][t][x] = {a,b,c};
} int mx3 = sz++;
dnc(mx, ex, sy, my, mx3);
mp.push_back(bint); dp.push_back(bbee);
for(int j=0; j<4; j++) w[j].push_back(bbee);
for(auto [x, cnt] : mp[t]) {
int tot1 = ex-mx+1, tot2 = ey-my;
int a = min(tot1, max(0, dp[mx3][w[2][t][x]][0]-(my-sy))) + min(tot2, max(0, dp[mx2][w[1][t][x]][0]-1));
int c = min(tot1, dp[mx3][w[2][t][x]][2]) + min(tot2, max(0, dp[mx2][w[1][t][x]][2]-(mx-sx)));
int b = tot1+tot2-a-c;
mp[sz][{a,b,c}] += cnt;
w[3][t][x] = {a,b,c};
} int mx4 = sz++;
dnc(mx, ex, my, ey, mx4);
for(auto [x, cnt] : mp[t]) {//if(sx==1&&ex==2&&sy==3&&ey==3) cout<<"YEE"<<dp[mx2][w[t][1][x]].a-(ey-my-1)<<endl;
int tot1 = my-sy, tot2 = mx-sx, tot3 = ex-mx+ey-my+1;
int a = min(tot1, dp[mx3][w[2][t][x]][0]) + min(tot2, max(0, dp[mx2][w[1][t][x]][0]-(ey-my+1))) + dp[mx4][w[3][t][x]][0];
int c = min(tot1, max(0, dp[mx3][w[2][t][x]][2]-(ex-mx+1))) + min(tot2, dp[mx2][w[1][t][x]][2]) + dp[mx4][w[3][t][x]][2];
int b = tot1+tot2+tot3-a-c;
dp[t][x] = {a,b,c};
}
for(int x : {mx1, mx2, mx3, mx4}) {
mp[x].clear(); dp[x].clear();
for(int j=0; j<4; j++) w[j][x].clear();
}
// cout<<sx<<bl<<ex<<bl<<sy<<bl<<ey<<" dp : "<<endl;
// for(auto [x,y] : dp[sz-1]) {
// cout<<x.a<<bl<<x.b<<bl<<x.c<<bl<<y.a<<bl<<y.b<<bl<<y.c<<endl;
// }
}
vector<pi> v;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int m, n; cin>>m>>n;
for(int i=1; i<m; i++) {
for(int j=1; j<m; j++) {
cin >> info[i][j];
}
}
for(int i=m-1; i; i--) v.push_back(pi(i, 0));
for(int j=0; j<m; j++) v.push_back(pi(0, j));
assert(v.size() == 2*m-1);
map<Bee, int> bint; map<Bee, Bee> bbee;
mp.push_back(bint); dp.push_back(bbee);
for(int j=0; j<4; j++) w[j].push_back(bbee);
for(int i=0; i<n; i++) {
int a,b,c; cin>>a>>b>>c;
mp[sz][{a,b,c}]++;
int x=0;
while(a--) {
pi t=v[x++]; res[t.ff][t.ss] += 0;
} while(b--) {
pi t=v[x++]; res[t.ff][t.ss] += 1;
} while(c--) {
pi t=v[x++]; res[t.ff][t.ss] += 2;
}
} sz++;
dnc(0, m-1, 0, m-1, 0);
for(int i=0; i<m; i++) {
for(int j=0; j<m; j++) cout<<res[i][j]+1<<bl;
cout<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |