oj.uz

Submission #53257

# Submission time Handle Problem Language Result Execution time Memory
53257 2018-06-29T06:01:06 Z 윤교준(#1402) Tram (CEOI13_tram) C++11
100 / 100
 76 ms 4588 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
int rd(int s, int e) { return rand()%(e-s+1) + s; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }
ll pw(ll n) { return n*n; }
ll dst(ll y0, ll x0, ll y1, ll x1) { return pw(y1-y0) + pw(x1-x0); }

const int MAXN = 150005;
const int MAXQ = 30005;

struct NOD {
	NOD(int s, int e, ll c, int y, int x)
		: s(s), e(e), c(c), y(y), x(x) {}
	int s, e;

	ll c;
	int y, x;

	bool operator < (const NOD &t) const {
		if(c != t.c) return c > t.c;
		if(y != t.y) return y < t.y;
		if(x != t.x) return x < t.x;
		if(s != t.s) return s < t.s;
		return e < t.e;
	}
	void f(int &_s, int &_e, int &_y, int &_x) const {
		_s = s; _e = e; _y = y; _x = x;
	}

	void print() {
		printf("%d %d :: %lld : %d %d\n", s, e, c, y, x);
	}
};

set<NOD> TQ;
set<int> TC;

bool B[MAXN][3];

int A[MAXQ];
int AnsY[MAXQ], AnsX[MAXQ];

int N, Q;

NOD f(int _s, int _e) {
	int s = max(1, _s), e = min(N, _e);
	int hy = -1, hx = -1; ll hl = -INFLL;

	vector<pii> HV;
	{
		int m = (s+e)/2;
		HV.eb(s, 1); HV.eb(s, 2);
		HV.eb(e, 1); HV.eb(e, 2);
		HV.eb(m, 1); HV.eb(m, 2);
		HV.eb(m+1, 1); HV.eb(m+1, 2);
	}

	vector<pii> TV;
	{
		if(B[s][1]) TV.eb(s, 1);
		if(B[s][2]) TV.eb(s, 2);
		if(B[e][1]) TV.eb(e, 1);
		if(B[e][2]) TV.eb(e, 2);
	}

	for(auto &hyx : HV) {
		int y, x; tie(y, x) = hyx;
		if(y < s || e < y || B[y][x]) continue;

		ll ret = INFLL;
		for(auto &tyx : TV) {
			ll t = dst(tyx.first, tyx.second, y, x);
			if(t < ret) ret = t;
		}

		if(hl < ret) {
			hl = ret;
			hy = y; hx = x;
		} else if(hl == ret && pii(y, x) < pii(hy, hx)) {
			hy = y; hx = x;
		}
	}

	return NOD(_s, _e, hl, hy, hx);
}

int main() {
	scanf("%d%d", &N, &Q);
	for(int i = 1; i <= Q; i++) {
		char c; scanf(" %c", &c);
		if('E' == c) {
			A[i] = -1;
			continue;
		}
		scanf("%d", &A[i]);
	}

	TC.insert(-INF); TC.insert(INF);
	TQ.insert(f(-INF, INF));

	for(int qi = 1; qi <= Q; qi++) {
		//printf("QUERY %d\n", qi);
		if(A[qi] < 0) {
			int s, e, y, x;
			for(; !TQ.empty();) {
				auto it = TQ.begin();
				if(B[it -> y][it -> x]) TQ.erase(it);
				else break;
			}
			TQ.begin() -> f(s, e, y, x);
			for(; !TQ.empty();) {
				auto it = TQ.begin();
				if(it -> y == y && it -> x == x) TQ.erase(it);
				else break;
			}
			AnsY[qi] = y; AnsX[qi] = x;
			//printf("GET ANS %d : %d %d\n", qi, y, x);
			//printf("s=%d, e=%d, y=%d, x=%d\n", s, e, y, x);

			if(B[y][1] || B[y][2]) {
				{
					NOD ret = f(s, y);
					auto it = TQ.find(ret);
					if(TQ.end() != it) TQ.erase(it);
				}

				{
					NOD ret = f(y, e);
					auto it = TQ.find(ret);
					if(TQ.end() != it) TQ.erase(it);
				}

				auto it = TC.lower_bound(y);

				{
					auto tt = it; tt--;
					NOD ret = f(*tt, y);
					auto qt = TQ.find(ret);
					if(TQ.end() != qt) TQ.erase(qt);
				}

				{
					auto tt = it;
					if(*tt == y) tt++;
					NOD ret = f(y, *tt);
					auto qt = TQ.find(ret);
					if(TQ.end() != qt) TQ.erase(qt);
				}
			}

			B[y][x] = true;

			if(s != y) {
				//printf("INSERT ");
				//f(s, y).print();
				TQ.insert(f(s, y));
			}
			if(e != y) {
				//printf("INSERT ");
				//f(y, e).print();
				TQ.insert(f(y, e));
			}

			TC.insert(y);

			{
				auto it = TC.find(y);

				{
					auto tt = it; tt--;
					TQ.insert(f(*tt, y));
				}

				{
					auto tt = it; tt++;
					TQ.insert(f(y, *tt));
				}
			}
		} else {
			int y = AnsY[A[qi]], x = AnsX[A[qi]];
			int s = -1, e = -1;
			auto tcit = TC.find(y);

			{
				auto utcit = tcit; utcit--;
				s = *utcit;

				NOD ret = f(s, y);
				auto it = TQ.find(ret);
				if(TQ.end() != it) TQ.erase(it);
			}

			{
				auto dtcit = tcit; dtcit++;
				e = *dtcit;

				NOD ret = f(y, e);
				auto it = TQ.find(ret);
				if(TQ.end() != it) TQ.erase(it);
			}

			B[y][x] = false;

			if(!B[y][1] && !B[y][2]) {
				TC.erase(y);
				TQ.insert(f(s, e));
			} else {
				TQ.insert(f(s, y));
				TQ.insert(f(y, e));
			}
		}
	}

	for(int i = 1; i <= Q; i++)
		if(A[i] < 0)
			printf("%d %d\n", AnsY[i], AnsX[i]);
	return 0;
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:130:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |   char c; scanf(" %c", &c);
      |           ~~~~~^~~~~~~~~~~
tram.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |   scanf("%d", &A[i]);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 492 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 492 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 3 ms 876 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1004 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 4 ms 876 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2552 KB Output is correct
2 Correct 64 ms 876 KB Output is correct
3 Correct 53 ms 1724 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4588 KB Output is correct
2 Correct 60 ms 876 KB Output is correct
3 Correct 66 ms 2156 KB Output is correct