QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#126656#4193. Joined Sessionscyb1010WA 2ms7876kbC++142.3kb2023-07-18 20:46:192023-07-18 20:46:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-18 20:46:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7876kb
  • [2023-07-18 20:46:19]
  • 提交

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'