QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#126207#4193. Joined Sessionscyb1010WA 2ms7824kbC++142.2kb2023-07-18 11:15:052023-07-18 11:15:07

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 11:15:07]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7824kb
  • [2023-07-18 11:15:05]
  • 提交

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);
    }
    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 = 1; j <= s && p; j++)
                f[i][s] = min(f[i][s], f[p][s - j]), p = cont[p];
        }
        ans[s] = f[n][s];
        for (int i = lst[n] + 1; i < n; i++) ans[s] = min(ans[s], f[i][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: 7688kb

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: 7588kb

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: 7824kb

input:

3
1 2
2 3
3 4

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 7660kb

input:

6
1 3
2 5
4 7
6 9
8 11
10 12

output:

1

result:

wrong answer 1st lines differ - expected: '3', found: '1'