oj.uz

답안 #126789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126789 2019-07-08T12:03:03 Z eriksuenderhauf 전차 (CEOI13_tram) C++11
100 / 100
 160 ms 14432 KB 
//#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

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.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 620 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 5 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 620 KB Output is correct
2 Correct 4 ms 420 KB Output is correct
3 Correct 6 ms 492 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2156 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 6 ms 1772 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2136 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 5 ms 1644 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 3436 KB Output is correct
2 Correct 81 ms 904 KB Output is correct
3 Correct 95 ms 3028 KB Output is correct

Subtask #8
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 14432 KB Output is correct
2 Correct 92 ms 876 KB Output is correct
3 Correct 114 ms 5356 KB Output is correct