oj.uz

Submission #120986

# Submission time Handle Problem Language Result Execution time Memory
120986 2019-06-25T21:19:26 Z luciocf Krave (COI14_krave) C++14
100 / 100
 927 ms 80208 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int inf = 1e9+10;

typedef long long ll;

set<int> tree[2][4*maxn];

int n, A, B;

void upd(int node, int l, int r, int a, int b, int v, bool q)
{
	if (l > r) return;
	if (l > b || r < a) return;

	if (l >= a && r <= b)
	{
		tree[q][node].insert(v);
		return;
	}

	int mid = (l+r)>>1;

	upd(2*node, l, mid, a, b, v, q); upd(2*node+1, mid+1, r, a, b, v, q);
}

// rightmost
int query1(int node, int l, int r, int pos, int x, bool q)
{
	if (l > r) return 0;
	int ans = 0;

	set<int>::iterator it = tree[q][node].upper_bound(x);
	if (tree[q][node].size() > 0 && it != tree[q][node].begin())
	{
		--it;
		ans = *it;
	}

	if (l == r) return ans;

	int mid = (l+r)>>1;

	if (pos <= mid) return max(ans, query1(2*node, l, mid, pos, x, q));
	return max(ans, query1(2*node+1, mid+1, r, pos, x, q));
}

// leftmost
int query2(int node, int l, int r, int pos, int x, bool q)
{
	if (l > r) return inf;
	int ans = inf;

	set<int>::iterator it = tree[q][node].lower_bound(x);
	if (tree[q][node].size() > 0 && it != tree[q][node].end())
		ans = *it;

	if (l == r) return ans;

	int mid = (l+r)>>1;

	if (pos <= mid) return min(ans, query2(2*node, l, mid, pos, x, q));
	return min(ans, query2(2*node+1, mid+1, r, pos, x, q));
}

int main(void)
{
	scanf("%d %d %d", &A, &B, &n);

	for (int i = 1; i <= n; i++)
	{
		int x, y, d;
		scanf("%d %d %d", &x, &y, &d);

		if (d == 1)
		{
			int l = query1(1, 1, B, y, x-1, 0);
			int r = min(A, query2(1, 1, B, y, x+1, 0));

			int h1 = min(B, query2(1, 1, A, x, y+1, 1));
			int h2 = query1(1, 1, A, x, y-1, 1);

			ll area1 = 1ll*(r-l)*(h1-y), area2 = 1ll*(r-l)*(y-h2);
			printf("%lld %lld\n", min(area1, area2), max(area1, area2));

			upd(1, 1, A, l, r, y, 1);
		}
		else
		{
			int l = query1(1, 1, A, x, y-1, 1);
			int r = min(B, query2(1, 1, A, x, y+1, 1));

			int h1 = min(A, query2(1, 1, B, y, x+1, 0));
			int h2 = query1(1, 1, B, y, x-1, 0);

			ll area1 = 1ll*(r-l)*(h1-x), area2 = 1ll*(r-l)*(x-h2);
			printf("%lld %lld\n", min(area1, area2), max(area1, area2));

			upd(1, 1, B, l, r, x, 0);
		}
	}
}

Compilation message

krave.cpp: In function 'int main()':
krave.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &A, &B, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
krave.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 38016 KB Output is correct
2 Correct 34 ms 37884 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 38264 KB Output is correct
2 Correct 41 ms 38776 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 42872 KB Output is correct
2 Correct 137 ms 43384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 42744 KB Output is correct
2 Correct 149 ms 44136 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 42716 KB Output is correct
2 Correct 166 ms 44920 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 51576 KB Output is correct
2 Correct 358 ms 66792 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 66020 KB Output is correct
2 Correct 394 ms 71468 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 65240 KB Output is correct
2 Correct 400 ms 76616 KB Output is correct
3 Correct 167 ms 45520 KB Output is correct
4 Correct 448 ms 73848 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 66212 KB Output is correct
2 Correct 442 ms 80208 KB Output is correct
3 Correct 178 ms 45688 KB Output is correct
4 Correct 478 ms 76292 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 66260 KB Output is correct
2 Correct 328 ms 70648 KB Output is correct
3 Correct 173 ms 45696 KB Output is correct
4 Correct 488 ms 78584 KB Output is correct