oj.uz

Submission #437529

# Submission time Handle Problem Language Result Execution time Memory
437529 2021-06-26T12:39:59 Z He_Ren Wombats (IOI13_wombats) C++
100 / 100
 10454 ms 71388 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 59844 KB Output is correct
2 Correct 70 ms 59940 KB Output is correct
3 Correct 155 ms 62360 KB Output is correct
4 Correct 92 ms 59844 KB Output is correct
5 Correct 69 ms 59940 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 88 ms 2524 KB Output is correct
12 Correct 1 ms 460 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 1956 KB Output is correct
2 Correct 325 ms 1956 KB Output is correct
3 Correct 334 ms 2004 KB Output is correct
4 Correct 329 ms 1956 KB Output is correct
5 Correct 333 ms 1956 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1593 ms 1948 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 67996 KB Output is correct
2 Correct 82 ms 67880 KB Output is correct
3 Correct 92 ms 67900 KB Output is correct
4 Correct 126 ms 69224 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 2024 KB Output is correct
2 Correct 325 ms 1944 KB Output is correct
3 Correct 332 ms 2036 KB Output is correct
4 Correct 324 ms 1988 KB Output is correct
5 Correct 325 ms 1972 KB Output is correct
6 Correct 86 ms 67892 KB Output is correct
7 Correct 76 ms 67892 KB Output is correct
8 Correct 90 ms 67816 KB Output is correct
9 Correct 130 ms 69280 KB Output is correct
10 Correct 78 ms 59912 KB Output is correct
11 Correct 71 ms 59844 KB Output is correct
12 Correct 150 ms 62284 KB Output is correct
13 Correct 96 ms 59828 KB Output is correct
14 Correct 68 ms 59920 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 2 ms 564 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 83 ms 2392 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 1600 ms 1948 KB Output is correct
28 Correct 2690 ms 69988 KB Output is correct
29 Correct 2530 ms 57720 KB Output is correct
30 Correct 2576 ms 57728 KB Output is correct
31 Correct 2748 ms 71088 KB Output is correct
32 Correct 1 ms 460 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 1956 KB Output is correct
2 Correct 320 ms 1948 KB Output is correct
3 Correct 328 ms 1960 KB Output is correct
4 Correct 325 ms 1952 KB Output is correct
5 Correct 324 ms 2056 KB Output is correct
6 Correct 80 ms 67900 KB Output is correct
7 Correct 77 ms 67848 KB Output is correct
8 Correct 90 ms 67896 KB Output is correct
9 Correct 121 ms 69188 KB Output is correct
10 Correct 69 ms 59844 KB Output is correct
11 Correct 68 ms 59884 KB Output is correct
12 Correct 151 ms 62340 KB Output is correct
13 Correct 89 ms 59820 KB Output is correct
14 Correct 72 ms 59844 KB Output is correct
15 Correct 2565 ms 69728 KB Output is correct
16 Correct 10454 ms 71388 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 81 ms 2440 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1607 ms 2044 KB Output is correct
30 Correct 2699 ms 70140 KB Output is correct
31 Correct 10204 ms 70624 KB Output is correct
32 Correct 10203 ms 70580 KB Output is correct
33 Correct 2531 ms 57708 KB Output is correct
34 Correct 9884 ms 58096 KB Output is correct
35 Correct 2572 ms 57796 KB Output is correct
36 Correct 9910 ms 58036 KB Output is correct
37 Correct 2742 ms 71180 KB Output is correct
38 Correct 10367 ms 71156 KB Output is correct
39 Correct 1 ms 460 KB Output is correct
40 Correct 10041 ms 57912 KB Output is correct