Submission #329404

#TimeUsernameProblemLanguageResultExecution timeMemory
329404shurongwangTram (CEOI13_tram)C++17
100 / 100
45 ms5412 KiB
#include <bits/stdc++.h> #define ln '\n' #define all(dat) dat.begin(), dat.end() #define loop(i, to) for (int i = 0; i < to; ++i) #define cont(i, to) for (int i = 1; i <= to; ++i) #define circ(i, fm, to) for (int i = fm; i <= to; ++i) #define foreach(i, dat) for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i) typedef long long num; using namespace std; const int nsz = 1.5e5, msz = 3e4; const num inf = 0x3f3f3f3f3f3f3f3f; int n, m; num dis[nsz + 5][2]; pair<int, int> pos[msz + 5]; num inline sqr(num a) { return a * a; } struct segment { bool c1[2], c2[2]; int r1, r2, r, c; num dis; segment() {} segment(int pos): r1(pos) {} segment(int r1, int r2): r1(r1), r2(r2) { c1[0] = c1[1] = c2[0] = c2[1] = 0; calc(); } segment(int r1, int r2, bool c1_0, bool c1_1, bool c2_0, bool c2_1): r1(r1), r2(r2) { c1[0] = c1_0, c1[1] = c1_1, c2[0] = c2_0, c2[1] = c2_1; calc(); } void inline upd(num d, int x, int y) { if (d != dis ? d > dis : (r != x ? x < r : y < c)) dis = d, r = x, c = y; } void inline calc() { dis = r = c = -1; int len = r2 - r1 + 1, md = (r1 + r2) >> 1; if (!c1[0] && !c1[1]) { num d = sqr(r2 - 1); upd(d + !c2[0], 1, 1), upd(d + !c2[1], 1, 2); } else if (!c2[0] && !c2[1]) { num d = sqr(n - r1); upd(d + !c1[0], n, 1), upd(d + !c1[1], n, 2); } else if (len & 1) { num d = sqr(md - r1); upd(min(d + !c1[0], d + !c2[0]), md, 1); upd(min(d + !c1[1], d + !c2[1]), md, 2); if (dis == 1 && !c1[0]) upd(1, r1, 1); if (dis == 1 && !c1[1]) upd(1, r1, 2); } else { num b1 = sqr(md - r1), b2 = sqr(r2 - md); upd(min(b1 + !c1[0], b2 + !c2[0]), md, 1); upd(min(b1 + !c1[1], b2 + !c2[1]), md, 2); upd(min(b2 + !c1[0], b1 + !c2[0]), md + 1, 1); upd(min(b2 + !c1[1], b1 + !c2[1]), md + 1, 2); } } }; struct compare1 { bool inline operator () (const segment &a, const segment &b) const { return a.dis != b.dis ? a.dis > b.dis : (a.r != b.r ? a.r < b.r : a.r1 < b.r1); } }; set<segment, compare1> s1; struct compare2 { bool inline operator () (const segment &a, const segment &b) const { return a.r1 < b.r1; } }; set<segment, compare2> s2; void inline ins() { int r = s1.begin()->r, c = s1.begin()->c - 1; vector<segment> d; for (segment s; s1.begin()->r == r && s1.begin()->c - 1 == c;) { s = *s1.begin(); s1.erase(s), s2.erase(s); if (r == s.r1 || r == s.r2) { s.c1[c] |= r == s.r1, s.c2[c] |= r == s.r2, s.calc(); d.push_back(s); } else { segment a(s.r1, r, s.c1[0], s.c1[1], !c, c), b(r, s.r2, !c, c, s.c2[0], s.c2[1]); d.push_back(a), d.push_back(b); } } loop (i, d.size()) s1.insert(d[i]), s2.insert(d[i]); } void inline del(int r, int c) { --c; if (r != 1 && r != n) { set<segment, compare2>::iterator it = s2.lower_bound(segment(r)); segment b = *it, a = *(--it); s1.erase(a), s1.erase(b), s2.erase(a), s2.erase(b); if (!a.c2[!c]) { segment s = segment(a.r1, b.r2, a.c1[0], a.c1[1], b.c2[0], b.c2[1]); s1.insert(s), s2.insert(s); } else { a.c2[c] = b.c1[c] = 0, a.calc(), b.calc(); s1.insert(a), s1.insert(b), s2.insert(a), s2.insert(b); } } else { segment s = *(r == 1 ? s2.begin() : --s2.end()); s1.erase(s), s2.erase(s); (r == 1 ? s.c1[c] : s.c2[c]) = 0, s.calc(); s1.insert(s), s2.insert(s); } } int main() { scanf("%d%d\n", &n, &m); s1.insert(segment(1, n)), s2.insert(segment(1, n)); cont (i, m) { int t; char cmd, tmp; scanf("%c%c", &cmd, &tmp); if (cmd == 'E') { segment s = *s1.begin(); pos[i] = make_pair(s.r, s.c); ins(); printf("%d %d\n", s.r, s.c); } else if (cmd == 'L') { scanf("%d\n", &t); del(pos[t].first, pos[t].second); } } }

Compilation message (stderr)

tram.cpp: In function 'void ins()':
tram.cpp:5:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define loop(i, to)        for (int i = 0; i < to; ++i)
......
   95 |  loop (i, d.size()) s1.insert(d[i]), s2.insert(d[i]);
      |        ~~~~~~~~~~~                            
tram.cpp:95:2: note: in expansion of macro 'loop'
   95 |  loop (i, d.size()) s1.insert(d[i]), s2.insert(d[i]);
      |  ^~~~
tram.cpp: In function 'int main()':
tram.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |  scanf("%d%d\n", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
tram.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |   scanf("%c%c", &cmd, &tmp);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
tram.cpp:132:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |    scanf("%d\n", &t);
      |    ~~~~~^~~~~~~~~~~~
#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...