Submission #437529

#	Time	Username	Problem	Language	Result	Execution time	Memory
437529		He_Ren	Wombats (IOI13_wombats)	C++98	100 / 100	10454 ms	71388 KiB

wombats

#include<bits/stdc++.h>
#include"wombats.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 5e3 + 5;
const int MAXM = 2e2 + 5;
const int B = 32;
const int MAXP = MAXN / B + 1;

int n,m;
int a[MAXN][MAXM], b[MAXN][MAXM];

struct Data
{
	int l, r, f[MAXM][MAXM];
	inline void rebuild(void)
	{
		memset(f,0x3f,sizeof(f));
		for(int i=1; i<=m; ++i) f[i][i] = 0;
		for(int k=l; k<=r; ++k)
		{
			for(int i=1; i<=m; ++i)
			{
				for(int j=m-1; j>=1; --j)
					f[i][j] = min(f[i][j], f[i][j+1] + a[k][j]);
				for(int j=2; j<=m; ++j)
					f[i][j] = min(f[i][j], f[i][j-1] + a[k][j-1]);
			}
			if(k == r) break;
			for(int i=1; i<=m; ++i)
				for(int j=1; j<=m; ++j)
					f[i][j] += b[k][j];
		}
	}
	inline void merge(const Data &p,const Data &q)
	{
		static int pt[MAXM][MAXM];
		memset(f,0x3f,sizeof(f));
		for(int k=-m+1; k<m; ++k)
			for(int i=1,j=i+k; i<=m; ++i, ++j) if(j >= 1 && j <= m)
			{
				int vl = j>1? pt[i][j-1]: 1, vr = i<m? pt[i+1][j]: m;
				for(int mid=vl; mid<=vr; ++mid)
				{
					int cur = p.f[i][mid] + q.f[mid][j];
					if(cur < f[i][j])
						f[i][j] = cur, pt[i][j] = mid;
				}
			}
	}
};

struct Segment_Tree
{
	Data tree[MAXP<<2];
	#define ls(u) ((u)<<1)
	#define rs(u) ((u)<<1|1)
	#define lson(u) ls(u),l,mid
	#define rson(u) rs(u),mid+1,r
	inline void push_up(int u){ tree[u].merge(tree[ls(u)], tree[rs(u)]);}
	void set_lr(int u,int l,int r,int q,int ql,int qr)
	{
		if(l == r){ tree[u].l = ql; tree[u].r = qr; return;}
		int mid = (l+r)>>1;
		if(q<=mid) set_lr(lson(u),q,ql,qr);
		else set_lr(rson(u),q,ql,qr);
	}
	void update(int u,int l,int r,int q)
	{
		if(l == r){ tree[u].rebuild(); return;}
		int mid = (l+r)>>1;
		if(q<=mid) update(lson(u),q);
		else update(rson(u),q);
		push_up(u);
	}
	int query(int x,int y){ return tree[1].f[x][y];}
}tree;

int pcnt, bid[MAXN];

void init(int _n,int _m,int _a[5000][200],int _b[5000][200])
{
	n = _n; m = _m;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<m; ++j) a[i][j] = _a[i-1][j-1];
	for(int i=1; i<n; ++i)
		for(int j=1; j<=m; ++j) b[i][j] = _b[i-1][j-1];
	
	pcnt = (n - 1 + B - 1) / B;
	int curp = 0; bid[n] = -1;
	for(int i=1,j; i<n; i=j)
	{
		j = min(n, i + B);
		tree.set_lr(1,1,pcnt, ++curp, i, j);
		tree.update(1,1,pcnt, curp);
		for(int k=i; k<j; ++k) bid[k] = curp;
	}
}

void changeH(int x,int y,int k)
{
	++x; ++y;
	a[x][y] = k;
	if(x < n) tree.update(1,1,pcnt, bid[x]);
	if(x > 1 && bid[x-1] != bid[x]) tree.update(1,1,pcnt, bid[x-1]);
}

void changeV(int x,int y,int k)
{
	++x; ++y;
	b[x][y] = k;
	tree.update(1,1,pcnt, bid[x]);
}

int escape(int x,int y)
{
	++x; ++y;
	return tree.query(x,y);
}

//#define He_Ren

#ifdef He_Ren

int main(void)
{
	int _n,_m;
	static int _a[5000][200], _b[5000][200];
	scanf("%d%d",&_n,&_m);
	for(int i=0; i<_n; ++i)
		for(int j=0; j<_m-1; ++j)
			scanf("%d",&_a[i][j]);
	for(int i=0; i<_n-1; ++i)
		for(int j=0; j<_m; ++j)
			scanf("%d",&_b[i][j]);
	
	init(_n,_m,_a,_b);
	
	int Q;
	scanf("%d",&Q);
	while(Q--)
	{
		int oper;
		scanf("%d",&oper);
		if(oper == 1)
		{
			int x,y,k;
			scanf("%d%d%d",&x,&y,&k);
			changeH(x,y,k);
		}
		else if(oper == 2)
		{
			int x,y,k;
			scanf("%d%d%d",&x,&y,&k);
			changeV(x,y,k);
		}
		else
		{
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%d\n",escape(x,y));
		}
	}
	return 0;
}

#endif

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24