Submission #126789

#	Time	Username	Problem	Language	Result	Execution time	Memory
126789		eriksuenderhauf	Tram (CEOI13_tram)	C++11	100 / 100	160 ms	14432 KiB

tram

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
int n, m, mrk[MAXN][2];
pii pos[MAXN];
set<int> cur;
set<pair<ll,pii>> act;

void upd(int l, int r, int m, int k) {
	for (int i = 0; i < 2; i++) {
		ll d1 = (ll) (m - l) * (m - l) + (l != -INF && !mrk[l][i]);
		ll d2 = (ll) (r - m) * (r - m) + (r != +INF && !mrk[r][i]);
		if (k == 1)
			act.insert(mp(-min(d1, d2), mp(m, i)));
		else
			act.erase(mp(-min(d1, d2), mp(m, i)));
	}
}

void upd(int l, int r, int k) {
	int mi = (l+r) / 2;
	mi = max(mi, 1); mi = min(mi, n);
	if (mi > max(l, 1))
		upd(l, r, mi - 1, k);
	if (mi < min(r, n))
		upd(l, r, mi + 1, k);
	upd(l, r, mi, k);
}

int main() {
	scanf("%d %d", &n, &m);
	cur.insert(-INF), cur.insert(INF);
	upd(-INF, INF, 1);
	for (int i = 1; i <= m; i++) {
		char t; scanf(" %c", &t);
		if (t == 'E') {
			pos[i] = (*act.begin()).se;
			auto it = cur.lower_bound(pos[i].fi);
			if (*it == pos[i].fi) {
				upd(*prev(it), *it, -1);
				upd(*it, *next(it), -1);
			} else
				upd(*prev(it), *it, -1);
			mrk[pos[i].fi][pos[i].se] = 1;
			cur.insert(pos[i].fi);
			it = cur.find(pos[i].fi);
			upd(*prev(it), *it, 1);
			upd(*it, *next(it), 1);
			printf("%d %d\n", pos[i].fi, pos[i].se+1);
		} else {
			int p; ni(p);
			auto it = cur.find(pos[p].fi);
			upd(*prev(it), *it, -1);
			upd(*it, *next(it), -1);
			mrk[pos[p].fi][pos[p].se] = 0;
			if (mrk[pos[p].fi][pos[p].se^1])  {
				upd(*prev(it), *it, 1);
				upd(*it, *next(it), 1);
			} else {
				upd(*prev(it), *next(it), 1);
				cur.erase(it);
			}
		}
	}
    return 0;
}

Compilation message (stderr)

tram.cpp: In function 'int main()':
tram.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:68:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   char t; scanf(" %c", &t);
      |           ~~~~~^~~~~~~~~~~
tram.cpp:9:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 | #define ni(n) scanf("%d", &(n))
      |               ~~~~~^~~~~~~~~~~~
tram.cpp:84:11: note: in expansion of macro 'ni'
   84 |    int p; ni(p);
      |           ^~

• 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