oj.uz

Submission #96831

# Submission time Handle Problem Language Result Execution time Memory
96831 2019-02-12T12:02:35 Z diamond_duke None (KOI17_shell) C++11
100 / 100
 1072 ms 48504 KB 
#include <algorithm>
#include <cstring>
#include <cstdio>
using ll = long long;
int n;
struct BIT
{
	int seg[2005];
	BIT() { memset(seg, 0, sizeof(seg)); }
	inline void modify(int pos, int x)
	{
		for (; pos <= n; pos += pos & -pos)
			seg[pos] += x;
	}
	inline int query(int pos)
	{
		int res = 0;
		for (; pos; pos -= pos & -pos)
			res += seg[pos];
		return res;
	}
} seg[2005];
int dp[2005][2005], arr[2005][2005], st[2005], en[2005];
inline int query(int x, int y) { return dp[x][y] + seg[x].query(y); }
int main()
{
	// freopen("KOI2017-T4.in", "r", stdin);
	scanf("%d", &n);
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			scanf("%d", arr[i] + j);
			dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
			ans += dp[i][j];
		}
	}
	printf("%lld\n", ans);
	for (int t = 0; t < n; t++)
	{
		char tp;
		int xx, yy;
		scanf(" %c%d%d", &tp, &xx, &yy);
		int x = xx, y = yy, d = tp == 'U' ? 1 : -1;
		memset(st, 0x3f, sizeof(st));
		memset(en, 0, sizeof(en));
		st[x] = en[x] = y;
		while (x <= n)
		{
			if (y < n && std::max(query(x - 1, y + 1), query(x, y)) + d ==
					std::max(query(x - 1, y + 1), query(x, y) + d))
				y++;
			else
				x++;
			en[x] = std::max(en[x], y);
		}
		x = xx;
		y = yy;
		while (y <= n)
		{
			if (x < n && std::max(query(x + 1, y - 1), query(x, y)) + d ==
					std::max(query(x + 1, y - 1), query(x, y) + d))
				x++;
			else
				y++;
			if (en[x] < y)
				break;
			st[x] = std::min(st[x], y);
		}
		for (int i = xx; i <= n; i++)
		{
			if (st[i] > en[i])
				continue;
			ans += (en[i] - st[i] + 1) * d;
			seg[i].modify(st[i], d);
			seg[i].modify(en[i] + 1, -d);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

shell.cpp: In function 'int main()':
shell.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shell.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", arr[i] + j);
    ~~~~~^~~~~~~~~~~~~~~~~~
shell.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d%d", &tp, &xx, &yy);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17024 KB Output is correct
2 Correct 18 ms 16896 KB Output is correct
3 Correct 17 ms 17024 KB Output is correct
4 Correct 18 ms 16996 KB Output is correct
5 Correct 17 ms 17024 KB Output is correct
6 Correct 17 ms 17024 KB Output is correct
7 Correct 15 ms 17024 KB Output is correct
8 Correct 17 ms 16888 KB Output is correct
9 Correct 20 ms 16908 KB Output is correct
10 Correct 17 ms 17024 KB Output is correct

Subtask #2
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 44116 KB Output is correct
2 Correct 261 ms 44116 KB Output is correct
3 Correct 377 ms 44096 KB Output is correct
4 Correct 362 ms 44164 KB Output is correct
5 Correct 357 ms 44152 KB Output is correct
6 Correct 292 ms 44252 KB Output is correct
7 Correct 225 ms 44024 KB Output is correct
8 Correct 425 ms 44280 KB Output is correct
9 Correct 414 ms 44124 KB Output is correct
10 Correct 319 ms 44024 KB Output is correct

Subtask #3
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 17024 KB Output is correct
2 Correct 18 ms 16896 KB Output is correct
3 Correct 17 ms 17024 KB Output is correct
4 Correct 18 ms 16996 KB Output is correct
5 Correct 17 ms 17024 KB Output is correct
6 Correct 17 ms 17024 KB Output is correct
7 Correct 15 ms 17024 KB Output is correct
8 Correct 17 ms 16888 KB Output is correct
9 Correct 20 ms 16908 KB Output is correct
10 Correct 269 ms 44116 KB Output is correct
11 Correct 261 ms 44116 KB Output is correct
12 Correct 377 ms 44096 KB Output is correct
13 Correct 362 ms 44164 KB Output is correct
14 Correct 357 ms 44152 KB Output is correct
15 Correct 292 ms 44252 KB Output is correct
16 Correct 225 ms 44024 KB Output is correct
17 Correct 425 ms 44280 KB Output is correct
18 Correct 414 ms 44124 KB Output is correct
19 Correct 319 ms 44024 KB Output is correct
20 Correct 565 ms 48276 KB Output is correct
21 Correct 574 ms 48376 KB Output is correct
22 Correct 506 ms 48184 KB Output is correct
23 Correct 1072 ms 48376 KB Output is correct
24 Correct 831 ms 48180 KB Output is correct
25 Correct 871 ms 48476 KB Output is correct
26 Correct 295 ms 44024 KB Output is correct
27 Correct 261 ms 44024 KB Output is correct
28 Correct 340 ms 48288 KB Output is correct
29 Correct 345 ms 48248 KB Output is correct
30 Correct 899 ms 48504 KB Output is correct
31 Correct 938 ms 48376 KB Output is correct
32 Correct 558 ms 44152 KB Output is correct
33 Correct 380 ms 44152 KB Output is correct
34 Correct 17 ms 17024 KB Output is correct