oj.uz

Submission #329404

# Submission time Handle Problem Language Result Execution time Memory
329404 2020-11-21T04:09:25 Z shurongwang Tram (CEOI13_tram) C++17
100 / 100
 45 ms 5412 KB 
#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

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);
      |    ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3052 KB Output is correct
2 Correct 41 ms 748 KB Output is correct
3 Correct 41 ms 2028 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5412 KB Output is correct
2 Correct 42 ms 776 KB Output is correct
3 Correct 37 ms 1960 KB Output is correct