Submission #328890

#	Time	Username	Problem	Language	Result	Execution time	Memory
328890		HCl_10	Tram (CEOI13_tram)	C++14	100 / 100	53 ms	6636 KiB

tram

/* by Hyperhydrochloric Acid */
#include <bits/stdc++.h>
using namespace std;
#define SZ(x)               ((int)(x).size())
#define all(x)              (x).begin(), (x).end()
#define loop(i, n)          for(int i = 0; i < (n); ++i)
#define cont(i, n)          for(int i = 1; i <= (n); ++i)
#define circ(i, a, b)       for(int i = (a); i <= (b); ++i)
#define range(i, a, b, c)   for(int i = (a); ((c) > 0 ? i <= (b) : i >= (b)); i += (c))
#define foreach(it, v)      for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
#define y0          y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1          y1II11II11III11I1III11II111IIII1II1I1
#define pub         push_back
#define pob         pop_back
#define mak         make_pair
typedef long long   ll;
typedef long double lf;
const int   Inf = 0x3f3f3f3f;
const ll    INF = 0x3f3f3f3f3f3f3f3fll;
/* Source code starts here */

ll inline Dist(int x, int y) {
	return 1ll * x * x + 1ll * y * y;
}

struct Cand {
	int x, y;
	ll dist;
	Cand(int x, int y, ll dist): x(x), y(y), dist(dist) {}
	bool operator<(const Cand &c) const {
		return mak(dist, mak(-x, -y)) < mak(c.dist, mak(-c.x, -c.y));
	}
};

int n, m;
set<Cand> T;
set<int> S;
int x[1 << 18], y[1 << 18];
int lgl[1 << 18];

void inline change(int l, int r, int mode) {
	if(!~l && !~r) return;
	if(!~l) {
		if(r == 1) return;
		Cand c(1, 1 + (lgl[r] == 1), Dist(r - 1, lgl[r] != 3));
		if(mode) T.insert(c);
		else T.erase(c);
	} else if(!~r) {
		if(l == n) return;
		Cand c(n, 1 + (lgl[l] == 1), Dist(n - l, lgl[l] != 3));
		if(mode) T.insert(c);
		else T.erase(c);
	} else {
		if(l + 1 == r) return;
		int mid = (l + r) >> 1;
		Cand mx(-1, -1, -Inf);
		loop(th, 2) {
			int nx = mid + th;
			if(nx >= r) break;
			loop(ny, 2) {
				Cand cd(nx, ny + 1, min(Dist(nx - l, !((lgl[l] >> ny) & 1)), Dist(r - nx, !((lgl[r] >> ny) & 1))));
				mx = max(mx, cd);
			}
		}
		if(mode) T.insert(mx);
		else T.erase(mx);
	}
}

int inline prev(int x) {
	set<int>::iterator it = S.lower_bound(x);
	if(it == S.begin()) return -1;
	else return *--it;
}

int inline succ(int x) {
	set<int>::iterator it = S.upper_bound(x);
	if(it == S.end()) return -1;
	else return *it;
}

// mode: 0 -- Erase, 1 -- Insert; update area between prev(x) and succ(x)
void inline control(int x, int mode) {
	int l = prev(x), r = succ(x);
	if(lgl[x]) change(l, x, mode), change(x, r, mode);
	else change(l, r, mode);
	if(lgl[x] == 1) {
		if(mode) T.insert(Cand(x, 2, 1));
		else T.erase(Cand(x, 2, 1));
	}
	if(lgl[x] == 2) {
		if(mode) T.insert(Cand(x, 1, 1));
		else T.erase(Cand(x, 1, 1));
	}
}

int main() {
	scanf("%d%d", &n, &m);
	cont(i, m) {
		char s; scanf(" %c", &s);
		if(s == 'E') {
			Cand cc(1, 1, 1);
			if(SZ(T)) {
				cc = *--T.end();
				T.erase(cc);
			}
			printf("%d %d\n", cc.x, cc.y);
			x[i] = cc.x, y[i] = cc.y;
			control(x[i], 0);
			lgl[x[i]] |= 1 << (y[i] - 1);
			S.insert(x[i]);
			control(x[i], 1);
		} else {
			int t; scanf("%d", &t);
			int X = x[t], Y = y[t];
			control(X, 0);
			lgl[X] ^= 1 << (Y - 1);
			if(!lgl[X]) S.erase(X);
			control(X, 1);
		}
	}
	return 0;
}

/**
 * 思考时间：17:00-18:00, 1h
 * 实现时间：18:00-18:40, 40min
 * 实现思路
 *  维护两个 set，分别表示有人的位置 S 和每一个可行的位置及与周围的距离 T
 *  查找的时候，直接使用 T 的最后一个元素
 *  修改的时候，对于一个插入操作，将插入的位置从 T 中删除，加入 S，并修改 T 的两端。
 *   对于一个删除操作，将删除的位置从 S 中删除，并加入 T。
 */

Compilation message (stderr)

tram.cpp: In function 'int main()':
tram.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:100:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |   char s; scanf(" %c", &s);
      |           ~~~~~^~~~~~~~~~~
tram.cpp:114:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |    int t; scanf("%d", &t);
      |           ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20