Submission #352596

#	Time	Username	Problem	Language	Result	Execution time	Memory
352596		arnold518	Krave (COI14_krave)	C++14	100 / 100	1030 ms	80364 KiB

krave

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12