oj.uz

Submission #120964

# Submission time Handle Problem Language Result Execution time Memory
120964 2019-06-25T20:17:44 Z luciocf Krave (COI14_krave) C++14
0 / 100
 3120 ms 99472 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

typedef pair<int, int> pii;
typedef long long ll;

struct node
{
	set<pii> st;
} tree[2][4*maxn];

int n, A, B;

bool ok(int node, int x, bool q)
{
	set<pii>::iterator it = tree[q][node].st.lower_bound({x+1, 0});
		
	if (it == tree[q][node].st.begin()) return false;
	--it;

	return (it->first <= x && it->second >= x);
}

void upd(int node, int l, int r, int pos, pii pp, bool q)
{
	tree[q][node].st.insert(pp);

	if (l == r) return;

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

	if (pos <= mid) upd(2*node, l, mid, pos, pp, q);
	else upd(2*node+1, mid+1, r, pos, pp, q);
}

// rightmost in range [a, b]
int query1(int node, int l, int r, int a, int b, int x, bool q)
{
	if (l > r) return -1;
	if (!ok(node, x, q)) return -1;

	if (l == r) return l;

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

	if (mid+1 > b) return query1(2*node, l, mid, a, b, x, q);

	int ans = query1(2*node+1, mid+1, r, a, b, x, q);
	if (ans == -1) ans = query1(2*node, l, mid, a, b, x, q);

	return ans; 
}

// leftmost in range [a, b]
int query2(int node, int l, int r, int a, int b, int x, bool q)
{
	if (l > r) return -1;
	if (!ok(node, x, q)) return -1;

	if (l == r) return l;

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

	if (mid < a) return query2(2*node+1, mid+1, r, a, b, x, q);

	int ans = query2(2*node, l, mid, a, b, x, q);
	if (ans == -1) ans = query2(2*node+1, mid+1, r, a, b, x, q);

	return ans; 
}

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, A, 1, x-1, y, 0);
			int r = query2(1, 1, A, x+1, A, y, 0);

			if (l == -1) l = 0;
			if (r == -1) r = A;

			int h1 = query2(1, 1, B, y+1, B, l, 1);
			int h2 = query1(1, 1, B, 1, y-1, l, 1);

			if (h1 == -1) h1 = B;
			if (h2 == -1) h2 = 0;

			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, B, y, {l, r}, 1);
		}
		else
		{
			int l = query1(1, 1, B, 1, y-1, x, 1);
			int r = query2(1, 1, B, y+1, B, x, 1);

			if (l == -1) l = 0;
			if (r == -1) r = B;

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

			if (h1 == -1) h1 = A;
			if (h2 == -1) h2 = 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, A, x, {l, r}, 0);
		}
	}
}

Compilation message

krave.cpp: In function 'int main()':
krave.cpp:77: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:82: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 38136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 38528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 416 ms 55400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 426 ms 55656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 463 ms 55736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1252 ms 68124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2987 ms 99472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2855 ms 98952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3120 ms 99072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2982 ms 97888 KB Output isn't correct
2 Halted 0 ms 0 KB -