QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#126656 | #4193. Joined Sessions | cyb1010 | WA | 2ms | 7876kb | C++14 | 2.3kb | 2023-07-18 20:46:19 | 2023-07-18 20:46:22 |
Judging History
answer
/**
* @author : cyb1010
* @date : 2023-07-18 10:11:09
* @file : trolcon.cpp
*/
#include <bits/stdc++.h>
using namespace std;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
int n, f[100010][5], lst[100010], cont[100010], ans[5];
struct seg {
int l, r;
seg() {}
seg(int _l, int _r) : l(_l), r(_r) {}
} a[100010];
set<pair<int, int>> s;
bool cmp(seg x, seg y) { return x.r < y.r; }
struct point {
int l, r, t;
} t[3000010];
int rt, tot, inf = 1000000000;
int mx(int x, int y) { return a[x].l > a[y].l ? y : x; }
void add(int &p, int l, int r, int k) {
if (!p)
p = ++tot, t[p].t = k;
t[p].t = mx(t[p].t, k);
if (l < r) {
int mid = l + r >> 1;
a[k].r <= mid ? add(t[p].l, l, mid, k) : add(t[p].r, mid + 1, r, k);
}
}
int qry(int p, int l, int r, int ll) {
if (r < ll || !p)
return 0;
if (l >= ll)
return t[p].t;
int mid = l + r >> 1;
return mx(qry(t[p].l, l, mid, ll), qry(t[p].r, mid + 1, r, ll));
}
int main() {
// fo("trolcon");
scanf("%d", &n), a[0].l = inf;
for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r);
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
auto x = s.lower_bound({a[i].l, 0});
if (x != s.begin())
lst[i] = (--x)->second;
cont[i] = qry(rt, 1, inf, a[i].l), add(rt, 1, inf, i);
s.emplace(a[i].r, i), !cont[i] ? cont[i] = i : 1;
}
for (int s = 0; s <= 3; s++) {
for (int i = 1; i <= n; i++) {
f[i][s] = f[lst[i]][s] + 1;
int p = cont[i];
for (int j = 0; j <= s; j++)
f[i][s] = min(f[i][s], f[lst[p]][s - j] + 1), p = cont[p];
// printf("%d ", f[i][s]);
}
// putchar('\n');
ans[s] = f[n][s];
// for (int i = lst[n] + 1; i < n; i++) ans[s] = min(ans[s], f[i][s]);
// printf("%d\n", ans[s]);
}
if (ans[1] < ans[0])
printf("1\n");
else if (ans[2] < ans[0])
printf("2\n");
else if (ans[3] < ans[0])
printf("3\n");
else
printf("impossible\n");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7796kb
input:
4 1 3 2 5 4 7 6 9
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7672kb
input:
5 1 3 4 7 8 10 2 5 6 9
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7876kb
input:
3 1 2 2 3 3 4
output:
impossible
result:
ok single line: 'impossible'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
6 1 3 2 5 4 7 6 9 8 11 10 12
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 7768kb
input:
8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 2ms
memory: 7652kb
input:
5 1 2 2 3 3 4 5 6 6 7
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
2 1 2 5 6
output:
impossible
result:
ok single line: 'impossible'
Test #8:
score: 0
Accepted
time: 2ms
memory: 7696kb
input:
2 1 3 2 4
output:
impossible
result:
ok single line: 'impossible'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5708kb
input:
5 3 5 2 7 1 10 6 8 9 11
output:
impossible
result:
ok single line: 'impossible'
Test #10:
score: 0
Accepted
time: 0ms
memory: 7872kb
input:
10 229 315 444 459 459 828 232 324 350 371 208 235 371 430 430 456 324 350 172 208
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 2ms
memory: 7868kb
input:
15 227 313 471 486 487 522 230 322 377 398 206 233 398 457 457 483 322 348 102 138 138 206 348 377 476 506 522 885 67 102
output:
1
result:
ok single line: '1'
Test #12:
score: -100
Wrong Answer
time: 1ms
memory: 5648kb
input:
20 261 347 505 520 521 556 264 356 411 432 240 267 432 491 491 517 356 382 136 172 172 240 382 411 510 540 556 579 67 102 579 931 22 80 69 136 271 327 11 53
output:
1
result:
wrong answer 1st lines differ - expected: '2', found: '1'