oj.uz

Submission #352596

# Submission time Handle Problem Language Result Execution time Memory
352596 2021-01-21T02:36:50 Z arnold518 Krave (COI14_krave) C++14
100 / 100
 1030 ms 80364 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1e5;
const int INF = 1e9;

int A, B;
int N;

struct SEG
{
	set<int> tree[MAXN*4+10];
	void update(int node, int tl, int tr, int l, int r, int q)
	{
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r)
		{
			tree[node].insert(q);
			return;
		}
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, q);
		update(node*2+1, mid+1, tr, l, r, q);
	}
	int queryh(int node, int tl, int tr, int p, int x)
	{
		int ret=INF;
		auto it=tree[node].lower_bound(x);
		if(it!=tree[node].end()) ret=min(ret, *it);
		if(tl==tr) return ret;
		int mid=tl+tr>>1;
		if(p<=mid) return min(ret, queryh(node*2, tl, mid, p, x));
		else return min(ret, queryh(node*2+1, mid+1, tr, p, x));
	}
	int queryl(int node, int tl, int tr, int p, int x)
	{
		int ret=-INF;
		auto it=tree[node].upper_bound(x);
		if(it!=tree[node].begin()) ret=max(ret, *(--it));
		if(tl==tr) return ret;
		int mid=tl+tr>>1;
		if(p<=mid) return max(ret, queryl(node*2, tl, mid, p, x));
		else return max(ret, queryl(node*2+1, mid+1, tr, p, x));
	}
}segx, segy;

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

	segx.update(1, 0, A, 0, A, 0);
	segx.update(1, 0, A, 0, A, B);
	segy.update(1, 0, B, 0, B, 0);
	segy.update(1, 0, B, 0, B, A);

	while(N--)
	{
		int x, y, d;
		scanf("%d%d%d", &x, &y, &d);

		int lx, rx, ly, ry;

		lx=segy.queryl(1, 0, B, y, x);
		rx=segy.queryh(1, 0, B, y, x);
		ly=segx.queryl(1, 0, A, x, y);
		ry=segx.queryh(1, 0, A, x, y);
		//printf("%d %d %d %d\n", lx, rx, ly, ry);

		if(d==1)
		{
			segx.update(1, 0, A, lx, rx, y);
			ll p=(ll)(rx-lx)*(y-ly);
			ll q=(ll)(rx-lx)*(ry-y);
			if(p>q) swap(p, q);
			printf("%lld %lld\n", p, q);
		}
		else
		{
			segy.update(1, 0, B, ly, ry, x);
			ll p=(ll)(ry-ly)*(x-lx);
			ll q=(ll)(ry-ly)*(rx-x);
			if(p>q) swap(p, q);
			printf("%lld %lld\n", p, q);
		}
	}
}

Compilation message

krave.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
krave.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   int mid=tl+tr>>1;
      |           ~~^~~
krave.cpp: In member function 'int SEG::queryh(int, int, int, int, int)':
krave.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid=tl+tr>>1;
      |           ~~^~~
krave.cpp: In member function 'int SEG::queryl(int, int, int, int, int)':
krave.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid=tl+tr>>1;
      |           ~~^~~
krave.cpp: In function 'int main()':
krave.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d%d", &A, &B);
      |  ~~~~~^~~~~~~~~~~~~~~~
krave.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
krave.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%d%d%d", &x, &y, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37996 KB Output is correct
2 Correct 27 ms 37996 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 38508 KB Output is correct
2 Correct 31 ms 38764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 43500 KB Output is correct
2 Correct 143 ms 43244 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 43500 KB Output is correct
2 Correct 149 ms 44140 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 43500 KB Output is correct
2 Correct 173 ms 44908 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 52176 KB Output is correct
2 Correct 390 ms 66796 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 67476 KB Output is correct
2 Correct 481 ms 71528 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 66412 KB Output is correct
2 Correct 410 ms 76680 KB Output is correct
3 Correct 175 ms 45444 KB Output is correct
4 Correct 487 ms 73788 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1030 ms 67608 KB Output is correct
2 Correct 472 ms 80364 KB Output is correct
3 Correct 181 ms 45804 KB Output is correct
4 Correct 503 ms 76268 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 949 ms 67564 KB Output is correct
2 Correct 348 ms 70532 KB Output is correct
3 Correct 188 ms 45804 KB Output is correct
4 Correct 552 ms 78316 KB Output is correct