Submission #328926

#TimeUsernameProblemLanguageResultExecution timeMemory
328926Mackerel_PikeTram (CEOI13_tram)C++14
100 / 100
72 ms17132 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...