#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long double ldb;
typedef long long int ll;
typedef unsigned long long int ull;
typedef complex<double> base;
ll mod=1e9+7;
struct node
{
int Ldx, Rdx, S, E; // L, R index, [S, E]
int a[202][202]; // u -> v minimum value
};
vector<node> nodes;
int R, C, Q;
int H[5020][202]; // H[i][j] : (i, j) -> (i, j+1)
int V[5020][202]; // V[i][j] : (i, j) -> (i+1, j)
void calc(int idx, int s, int e) // naive calc
{
int dp_1[202][202]={0}, dp_2[202][202]={0};
int CV[202][202]={0}, OPT[202][202]={0}, PS[202]={0}, i, j, k, u, v;
for(i=1 ; i<=C ; i++)
{
for(j=1 ; j<=C ; j++)
{
if(i==j) dp_1[i][j]=0;
else dp_1[i][j]=1e9+7;
}
}
for(i=s ; i<=e ; i++)
{
for(j=1 ; j<=C-1 ; j++) PS[j]=PS[j-1]+H[i][j];
for(j=1 ; j<=C ; j++)
{
for(k=1 ; k<=C ; k++)
{
OPT[j][k]=0;
if(j==k) CV[j][k]=0+V[i][k];
if(j<k) CV[j][k]=PS[k-1]-PS[j-1]+V[i][k];
if(j>k) CV[j][k]=PS[j-1]-PS[k-1]+V[i][k];
}
}
for(k=1-C ; k<=C ; k++)
{
for(u=1 ; u<=C ; u++)
{
v=u+k; if(v<1 || v>C) continue;
dp_2[u][v]=1e9+7;
int l=OPT[u][v-1]?OPT[u][v-1]:1;
int r=OPT[u+1][v]?OPT[u+1][v]:C;
for(j=l ; j<=r ; j++)
if(dp_2[u][v]>dp_1[u][j]+CV[j][v])
OPT[u][v]=j, dp_2[u][v]=dp_1[u][j]+CV[j][v];
}
}
for(j=1 ; j<=C ; j++)
for(k=1 ; k<=C ; k++)
dp_1[j][k]=dp_2[j][k];
}
for(i=1 ; i<=C ; i++)
for(j=1 ; j<=C ; j++)
nodes[idx].a[i][j]=dp_1[i][j];
return;
}
void merger(int idx, int Ldx, int Rdx, int s, int e)
{
int OPT[202][202]={0}, dp[202][202], i, j, k, v;
for(k=1-C ; k<=C ; k++)
{
for(i=1 ; i<=C ; i++)
{
j=i+k; dp[i][j]=1e9+7;
int l=OPT[i][j-1]?OPT[i][j-1]:1;
int r=OPT[i+1][j]?OPT[i+1][j]:C;
for(v=l ; v<=r ; v++)
if(dp[i][j]>nodes[Ldx].a[i][v]+nodes[Rdx].a[v][j])
OPT[i][j]=v, dp[i][j]=nodes[Ldx].a[i][v]+nodes[Rdx].a[v][j];
}
}
for(i=1 ; i<=C ; i++)
for(j=1 ; j<=C ; j++)
nodes[idx].a[i][j]=dp[i][j];
}
void build(int idx, int s, int e)
{
node X; X.Ldx=-1; X.Rdx=-1; X.S=s; X.E=e;
nodes.push_back(X);
if(e-s<20) { calc(nodes.size()-1, s, e); return; }
int m=(s+e)>>1;
if(nodes[idx].Ldx==-1)
{
nodes[idx].Ldx=nodes.size();
build(nodes.size(), s, m);
}
if(X.Rdx==-1)
{
nodes[idx].Rdx=nodes.size();
build(nodes.size(), m+1, e);
}
merger(idx, nodes[idx].Ldx, nodes[idx].Rdx, s, e);
}
void update(int idx, int s, int e, int l, int r)
{
if(l>e || r<s) return;
if(e-s<20) { calc(idx, s, e); return; }
int m=(s+e)>>1;
if(nodes[idx].Ldx!=-1) update(nodes[idx].Ldx, s, m, l, r);
if(nodes[idx].Rdx!=-1) update(nodes[idx].Rdx, m+1, e, l, r);
merger(idx, nodes[idx].Ldx, nodes[idx].Rdx, s, e);
}
int main(void)
{
fio; int i, j, whi, u, v, w; cin>>R>>C;
for(i=1 ; i<=R ; i++)
for(j=1 ; j<=C-1 ; j++) cin>>H[i][j];
for(i=1 ; i<=R-1 ; i++)
for(j=1 ; j<=C ; j++) cin>>V[i][j];
build(0, 1, R); cin>>Q;
while(Q--)
{
cin>>whi;
if(whi==1) { cin>>u>>v>>w; H[u+1][v+1]=w; update(0, 1, R, u+1, u+1); }
if(whi==2) { cin>>u>>v>>w; V[u+1][v+1]=w; update(0, 1, R, u+1, u+2); }
if(whi==3) { cin>>u>>v; cout<<nodes[0].a[u+1][v+1]<<"\n"; }
}
return 0;
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
/tmp/ccOafeni.o: In function `main':
wombats.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccrorC2g.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccrorC2g.o: In function `main':
grader.c:(.text.startup+0x103): undefined reference to `init'
grader.c:(.text.startup+0x164): undefined reference to `escape'
grader.c:(.text.startup+0x1cf): undefined reference to `changeH'
grader.c:(.text.startup+0x23b): undefined reference to `changeV'
collect2: error: ld returned 1 exit status
