#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double Lf;
typedef pair<ll, int> pii;
const int maxn = 1.5e5 + 5;
const int maxq = 3e4 + 5;
const int maxl = 15;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, q;
int ans[maxn];
class Data{
public:
int lid, lmsk, rid, rmsk;
pii res;
Data(){}
Data(int lid_, int lmsk_, int rid_, int rmsk_, pii res_): lid(lid_), lmsk(lmsk_), rid(rid_), rmsk(rmsk_), res(res_){}
};
inline bool comp(const pii &a, const pii &b){ return MP(a.fst, MP(-a.snd % n, -a.snd / n)) < MP(b.fst, MP(-b.snd % n, -b.snd / n)); }
inline pii max(const pii &a, const pii &b){ return comp(a, b) ? b : a; }
inline ll dis(int id, int msk, int x, int y){
return 1ll * abs(id - x) * abs(id - x) + (((1 << y) & msk) == 0);
}
inline pii calc(int lid, int lmsk, int rid, int rmsk){
pii ret = MP(-INF, -1);
if(!~lid || !~rid || lid == rid - 1)
return ret;
int x = (lid + rid) >> 1, y = 0;
FOR(i, 0, 2) FOR(j, 0, 2){
pii cur = MP(min(dis(lid, lmsk, x + i, y + j), dis(rid, rmsk, x + i, y + j)), (y + j) * n + (x + i));
ret = max(ret, cur);
}
return ret;
}
inline Data operator + (const Data &a, const Data &b){
Data c;
c.lid = (!~a.lid ? b.lid : a.lid), c.lmsk = (!~a.lid ? b.lmsk : a.lmsk);
c.rid = (!~b.rid ? a.rid : b.rid); c.rmsk = (!~b.rid ? a.rmsk : b.rmsk);
c.res = max(a.res, b.res);
c.res = max(c.res, calc(a.rid, a.rmsk, b.lid, b.lmsk));
return c;
}
class SegmentTree{
private:
static const int siz = 262144;
public:
Data dat[siz << 1];
inline int size(){ return siz; }
inline void build(int x, int l, int r){
if(l == r){
dat[x] = Data(-1, 0, -1, 0, MP(-INF, l));
return;
}
int md = l + r >> 1;
build(x << 1, l, md);
build(x << 1 | 1, md + 1, r);
dat[x] = dat[x << 1] + dat[x << 1 | 1];
return;
}
inline void update(int x, int l, int r, int y){
if(l == r){
int row = y / n;
dat[x].lmsk ^= (1 << row);
dat[x].rmsk ^= (1 << row);
dat[x].lid = dat[x].rid = (dat[x].lmsk ? l : -1);
if(dat[x].lmsk != 3){
dat[x].res = MP(1, ((dat[x].lmsk & 1) ? 1 : 0) * n + l);
}
else
dat[x].res = MP(-INF, -1);
return;
}
int md = l + r >> 1;
int column = y % n;
if(column <= md)
update(x << 1, l, md, y);
else
update(x<< 1 | 1, md + 1, r, y);
dat[x] = dat[x << 1] + dat[x << 1 | 1];
return;
}
} seg;
int main(){
scanf("%d%d", &n, &q);
seg.build(1, 0, seg.size() - 1);
FOR(i, 0, q){
char buf[maxl]; scanf("%s", buf);
if(buf[0] == 'E'){
Data fuck = seg.dat[1];
pii vl, vr;
if(!~fuck.lid && !~fuck.rid)
fuck.res = MP(INF, 0);
else{
if(fuck.lid){
int &lid = fuck.lid, &lmsk = fuck.lmsk;
if(fuck.lmsk != 3)
vl = MP(1ll * lid * lid + 1, ((lmsk & 1) ? 1 : 0) * n + 0);
else
vl = MP(1ll * lid * lid, 0);
fuck.res = max(fuck.res, vl);
}
if(fuck.rid != n - 1){
int &rid = fuck.rid, &rmsk = fuck.rmsk;
if(fuck.rmsk != 3)
vr = MP(1ll * (n - rid - 1) * (n - rid - 1) + 1, ((rmsk & 1) ? 1 : 0) * n + n - 1);
else
vr = MP(1ll * (n - rid - 1) * (n - rid - 1), n - 1);
fuck.res = max(fuck.res, vr);
}
}
printf("%d %d\n", fuck.res.snd % n + 1, fuck.res.snd / n + 1);
seg.update(1, 0, seg.size() - 1, fuck.res.snd);
ans[i] = fuck.res.snd;
}
else{
int x; scanf("%d", &x); --x;
seg.update(1, 0, seg.size() - 1, ans[x]);
}
}
return 0;
}
Compilation message
tram.cpp: In member function 'void SegmentTree::build(int, int, int)':
tram.cpp:75:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int md = l + r >> 1;
| ~~^~~
tram.cpp: In member function 'void SegmentTree::update(int, int, int, int)':
tram.cpp:94:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int md = l + r >> 1;
| ~~^~~
tram.cpp: In function 'int main()':
tram.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
107 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:112:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
112 | char buf[maxl]; scanf("%s", buf);
| ~~~~~^~~~~~~~~~~
tram.cpp:141:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
141 | int x; scanf("%d", &x); --x;
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
19 ms |
16748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
20 ms |
16748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
20 ms |
16876 KB |
Output is correct |
| 3 |
Correct |
22 ms |
16748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
29 ms |
16748 KB |
Output is correct |
| 3 |
Correct |
24 ms |
16876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
20 ms |
16748 KB |
Output is correct |
| 3 |
Correct |
20 ms |
16748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
21 ms |
16748 KB |
Output is correct |
| 3 |
Correct |
21 ms |
16748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
17132 KB |
Output is correct |
| 2 |
Correct |
45 ms |
17004 KB |
Output is correct |
| 3 |
Correct |
53 ms |
17004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
17132 KB |
Output is correct |
| 2 |
Correct |
55 ms |
16876 KB |
Output is correct |
| 3 |
Correct |
72 ms |
17004 KB |
Output is correct |
