Submission #418115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
418115	2021-06-05T06:07:47 Z	Kevin_Zhang_TW	Arranging Tickets (JOI17_arranging_tickets)	C++17	0 / 100	1 ms	312 KB

arranging_tickets

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;

int n, m;

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	vector<tuple<int,int,int>> req(m);
	for (auto &[l, r, c] : req) {
		cin >> l >> r >> c;
		if (l > r) swap(l, r);
		--r;
		assert(c == 1);
	}
	sort(AI(req));

	int res = 0;

	vector<int> sum(n + 1);

	for (auto [l, r, c] : req) {
		for (int i = l;i <= r;++i)
			++sum[i];
	}
	debug(AI(sum));

	while (true) {
		int ch = -1;
		for (int i = 0;i < m;++i) {
			auto &[l, r, c] = req[i];
			int a = 0, b = 0;
			for (int j = 1;j <= n;++j) {
				chmax((l<=j&&j<=r?a:b), sum[j]);
			}
			DE(l, r, c, a, b);
			if (c == 1 && b + 1 < a)
				ch = i;
			if (c == 0 && a + 1 < b)
				ch = i;
		}
		DE(ch);

		if (ch == -1) break;

		auto &[l, r, c] = req[ch];
		for (int j = 1;j <= n;++j) {
			if ((l<=j&&j<=r) == c)
				sum[j]--;
			else
				sum[j]++;
		}
		c ^= 1;
	}

	debug(AI(sum));

	cout << *max_element(AI(sum)) << '\n';
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	312 KB	Output is correct
12	Incorrect	1 ms	204 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #2

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	312 KB	Output is correct
12	Incorrect	1 ms	204 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	312 KB	Output is correct
12	Incorrect	1 ms	204 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	312 KB	Output is correct
12	Incorrect	1 ms	204 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	312 KB	Output is correct
12	Incorrect	1 ms	204 KB	Output isn't correct
13	Halted	0 ms	0 KB	-