QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#877177#10042. SchedulingzhaohaikunWA 94ms9812kbC++236.8kb2025-01-31 20:08:262025-01-31 20:08:26

Judging History

你现在查看的是最新测评结果

  • [2025-01-31 20:08:26]
  • 评测
  • 测评结果：WA
  • 用时：94ms
  • 内存：9812kb
查看
  • [2025-01-31 20:08:26]
  • 提交

answer

// MagicDark
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lc num << 1
#define rc lc | 1
#define li lc, l, mid
#define ri rc, mid + 1, r
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T &x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T &x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = - f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 1e6 + 10, inf = 1e9;
int n, l[N], r[N], m;
vector <int> v[N];
vector <pair <int, int>> vv[N];
// int tag[N << 2];
// pair <int, int> info[N << 2];
// void build(int num, int l, int r) {
// 	info[num] = make_pair(- r, r);
// 	if (l == r) return;
// 	build(li), build(ri);
// }
// void down(int num, int x) {
// 	tag[num] += x;
// }
// void pushdown(int num) {
// 	if (tag[num]) {
// 		down(lc, tag[num]), down(rc, tag[num]);
// 		tag[num] = 0;
// 	}
// }
// void pushup(int num) {
// 	info[num] = max(info[lc], info[rc]);
// }
// void change(int num, int l, int r, int L, int R, int x) {
// 	if (l == r) return down(num, x);
// 	pushdown(num);
// 	if (mid >= L) change(li, L, R, x);
// 	if (mid < R) change(ri, L, R, x);
// 	pushup(num);
// }
// bool vis[N];
int ss[N], ans[N];
void zhk() {
	read(n);
	set <pair <int, int>> s;
	F(i, 1, n) {
		ans[i] = 0;
		read(l[i]), read(r[i])--;
		F(_, 1, 3) {
			auto pos = s.lower_bound(make_pair(l[i], inf));
			int tl = l[i], tr = l[i];
			if (pos != s.begin()) {
				auto pp = prev(pos);
				if (pp -> second + 1 >= l[i]) {
					tl = pp -> first;
					tr = pp -> second + 1;
					s.erase(pp);
				}
			}
			// int tr = tl;
			// auto pp = next(pos);
			if (pos != s.end() && pos -> first == tr + 1) {
				tr = pos -> second;
				s.erase(pos);
			}
			s.emplace(tl, tr);
			// for (auto [l, r]: s) debug << l << ' ' << r << '\n';
			// debug << endl;
		}
	}
	vector <int> w;
	// for (auto [l, r]: s) {
	// 	debug << l << " " << r << endl;
	// }
	for (auto [l, r]: s)
		F(i, l, r) {
			// debug << i << endl;
			w.push_back(i);
		}
	m = w.size();
	set <int> g;
	F(i, 1, m + 5) g.insert(i), v[i].clear(), vv[i].clear();
	F(i, 0, m + 1) ss[i] = 0;
	F(i, 1, n) {
		l[i] = lower_bound(all(w), l[i]) - w.begin() + 1;
		r[i] = upper_bound(all(w), r[i]) - w.begin();
		// debug << l[i] << ' ' << r[i] << endl;
		v[r[i]].push_back(l[i]);
		vv[l[i]].emplace_back(r[i], i);
	}
	F(i, 1, m) {
		for (int j: v[i]) {
			auto it = g.upper_bound(j);
			// debug << "@ " << i << " " << j << " " << * it << endl;
			F(_, 1, 2) {
				if (* it == i + 3) {
					puts("-1");
					return;
				}
				it = g.erase(it);
			}
		}
		auto pos = prev(g.lower_bound(i + 3));
		int w = * pos;
		if (w <= i) {
			// debug << w << " " << i << endl;
			ss[w]++, ss[i + 2]--;
		}
		// assert(pos)
	}
	priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
	vector <int> gg;
	F(i, 1, m) {
		if (i > 1) ss[i] += ss[i - 2];
		if (ss[i]) gg.push_back(i);
	}
	// for (int i: gg) cout << i << ' '; debug << endl;
	if (gg.empty()) {
		for (int i = 1; i <= m; i += 2) ss[i] = 1;
	} else {
		// int cur = 1;
		vector <int> stk;
		int mx = 0;
		auto upd = [&] (int x) {
			// debug << "@ " << x << endl;
			for (int j: v[x]) {
				// debug << "! " << x << " " << j << endl;
				auto it = g.upper_bound(j);
				if (it == g.end() || (mx > x && * it > x)) return false;
				chkmax(mx, * it);
				stk.push_back(* it);
				g.erase(it);
			}
			return true;
		};
		g.clear();
		for (int i = gg.front() - 2; i >= 1; i -= 2) ss[i] = 1, g.insert(i);
		g.insert(gg.front());
		F(i, 1, gg.front() - 1) {
			if (!upd(i)) {
				// debug << "@\n";
				puts("-1");
				return;
			}
		}
		F(i, 0, SZ(gg) - 1) {
			// g.insert(gg[i]);
			g.insert(gg[i + 1]);
			if (!upd(gg[i])) {
				// debug << "@\n";
				puts("-1");
				return;
			}
			bool flag = false;
			if ((gg[i + 1] - gg[i] - 1) & 1) {
				for (int j = gg[i] + 2; j + 1 < gg[i + 1]; j += 2) {
					ss[j] = 1;
					if (g.empty() || * g.rbegin() != gg[i + 1]) {
						g.insert(gg[i + 1]);
						mx = j;
					} else {
						g.insert(j);
					}
				}
			} else {
				for (int j = gg[i] + 3; j + 1 < gg[i + 1]; j += 2) {
					ss[j] = 1;
					// debug << "# " << j << endl;
					g.insert(j);
					if (g.empty() || * g.rbegin() != gg[i + 1]) {
						g.insert(gg[i + 1]);
						mx = j;
					} else {
						g.insert(j);
					}
				}
				int pos = stk.size(), mm = mx;
				flag = true;
				F(j, gg[i] + 1, gg[i + 1] - 1) {
					if (!upd(j)) {
						if ((j - gg[i]) & 1 || j == gg[i + 1] - 1) {
							// debug << "@\n";
							puts("-1");
							return;
						}
						flag = false;
						mx = mm;
						// ss[j + 1] = 0;
						while (stk.size() > pos) {
							int x = stk.front(); stk.pop_back();
							g.insert(x);
						}
						bool flag = false;
						for (int k = gg[i] + 3; k <= j + 1; k += 2) {
							ss[k] = 0;
							if (!g.erase(k)) {
								flag = true;
								assert(!g.count(gg[i + 1]));
								g.insert(gg[i + 1]);
							}
						}
						for (int k = gg[i] + 2; k <= j; k += 2) {
							ss[k] = 1;
							g.insert(k);
						}
						if (flag) {
							g.erase(g.upper_bound(gg[i]));
						}
						break;
					}
				}
			}
			if (flag) {
				F(j, gg[i] + 1, gg[i + 1] - 1) {
					if (!upd(j)) {
						// debug << "! " << j << endl;
						puts("-1");
						return;
					}
				}
			}
		}
		for (int i = gg.back() + 2; i <= m; i += 2) ss[i] = 1, g.insert(i);
	}
	F(i, 1, m - 1)
		if (ss[i] && ss[i + 1]) {
			puts("-1");
			return;
		}
	F(i, 1, m) {
		// if (!ss[i - 1] && !ss[i + 1]) ss[i] = 1;
		for (auto t: vv[i]) q.push(t);
		if (ss[i]) {
			// debug << "@ " << i << endl;
			if (q.size()) {
				auto [a, b] = q.top(); q.pop();
				if (a < i) {
					puts("-1");
					return;
				}
				assert(a >= i);
				ans[b] = i;
			}
		}
	}
	// for (int i: w) cout << i << ' '; cout << '\n';
	assert(q.empty());
	F(i, 1, n) assert(ans[i]);
	F(i, 1, n) cout << w[ans[i] - 1] << ' '; cout << '\n';
}
signed main() {
	int _ = 1;
	cin >> _;
	// if (_ == 50004) {
	// 	F(i, 1, _) {
	// 		int n;
	// 		cin >> n;
	// 		F(j, 1, n) {
	// 			cin >> l[i] >> r[i];
	// 		}
	// 		if (i == 1619) {
	// 			cout << n << '\n';
	// 			F(i, 1, n) cout << l[i] << ' ' << r[i] << '\n';
	// 		}
	// 	}
	// }
	while (_--) zhk();
	return 0;
}
/* why?
*/
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 9804kb

input:

4
3
1 3
1 7
2 4
2
1 2
2 3
4
1 5
2 6
3 4
4 7
2
1 5
2 3

output:

1 5 3 
-1
-1
4 2

result:

ok Valid schedules (4 test cases)

Test #2:

score: 0
Accepted
time: 3ms
memory: 9812kb

input:

5
1
1 2
1
2 4
2
2 3
1 2
2
3 4
1 2
3
1 5
2 4
3 4

output:

1 
2 
-1
3 1 
-1

result:

ok Valid schedules (5 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 9812kb

input:

1
5
2 3
9 10
1 7
5 11
5 7

output:

-1

result:

ok Valid schedules (1 test case)

Test #4:

score: 0
Accepted
time: 94ms
memory: 9808kb

input:

100000
2
3 10
2 3
2
8 10
4 7
2
1 3
2 8
2
8 10
6 8
2
3 5
3 4
2
1 9
1 7
2
7 9
1 10
2
5 7
3 8
2
9 10
4 10
2
4 10
3 6
2
2 9
3 9
2
3 4
5 7
2
5 6
1 2
2
2 8
4 10
2
2 4
1 10
2
4 7
2 10
2
3 7
9 10
2
6 9
1 5
2
3 9
5 8
2
3 10
5 8
2
3 5
1 6
2
8 9
7 10
2
1 7
3 4
2
3 6
5 8
2
2 8
1 3
2
3 5
4 9
2
3 8
2 5
2
3 4
6 9
...

output:

4 2 
9 4 
1 3 
8 6 
-1
1 3 
8 1 
5 3 
9 5 
5 3 
2 4 
3 5 
5 1 
2 4 
3 1 
4 2 
4 9 
7 1 
3 5 
3 5 
3 1 
-1
1 3 
3 5 
3 1 
3 5 
4 2 
3 7 
2 7 
4 6 
6 1 
4 2 
7 2 
6 4 
6 8 
2 8 
7 2 
3 1 
4 2 
5 3 
3 5 
3 5 
3 1 
1 8 
5 7 
9 7 
2 4 
6 8 
1 5 
4 6 
6 3 
3 5 
4 9 
3 5 
5 3 
8 6 
1 6 
5 3 
8 2 
2 5 
-1
-...

result:

ok Valid schedules (100000 test cases)

Test #5:

score: -100
Wrong Answer
time: 89ms
memory: 9812kb

input:

50004
5
6 8
4 7
7 9
7 8
7 10
5
5 8
4 8
1 7
5 7
4 6
5
9 10
7 10
1 6
1 6
2 3
5
4 10
4 10
1 9
6 9
7 8
5
3 7
1 6
1 4
2 4
4 10
4
1 7
1 7
3 5
2 8
4
2 4
1 6
2 4
2 6
4
8 10
2 3
6 9
9 10
5
1 9
5 8
2 3
3 10
1 2
5
1 2
2 8
8 10
3 7
4 10
3
2 6
9 10
1 8
3
9 10
1 5
3 5
4
2 6
1 10
1 3
1 4
3
5 10
2 10
2 3
5
5 6
1 10...

output:

-1
-1
-1
-1
-1
1 5 3 7 
-1
-1
-1
1 5 9 3 7 
3 9 1 
9 1 3 
5 7 1 3 
6 4 2 
-1
-1
3 5 1 
3 7 5 1 9 
-1
-1
5 7 3 9 
5 1 3 9 7 
9 5 3 7 1 
-1
-1
6 4 8 2 
7 5 3 
3 7 1 
6 8 2 
7 3 5 9 1 
-1
-1
3 1 5 
-1
7 3 1 5 
1 3 7 
1 5 3 
4 6 2 
-1
-1
-1
-1
-1
5 3 7 1 9 
7 3 9 1 5 
5 1 7 3 
3 5 1 
-1
-1
8 6 4 
5 3 7 ...

result:

wrong answer jury found an answer, participant did not (test case 1701)
English 繁體中文 简体中文

伺服器時間: 2025-02-02 04:40:45 | 開源專案