//#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);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
