QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110410#2559. Endless RoadyllcmWA 4ms9760kbC++144.8kb2023-06-01 21:43:112023-06-01 21:43:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-01 21:43:12]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9760kb
  • [2023-06-01 21:43:11]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
#define int long long
using namespace std;
inline int read() {
    int x = 0; bool op = 0;
    char c = getchar();
    while(!isdigit(c))op |= (c == '-'), c = getchar();
    while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return op ? -x : x;
}
const int N = 2.5e5 + 10;
const int INF = 1e18;
int n;
struct Node {
    int id, l, r;
    Node() {}
    Node(int id, int l, int r):id(id), l(l), r(r) {}
    bool operator < (const Node &tmp) const {return (r != tmp.r ? r < tmp.r : (l != tmp.l ? l > tmp.l : id < tmp.id));}
}a[N];
int tot, lsh[N << 1];
void disc() {
    for(int i = 1; i <= n; i++)lsh[++tot] = a[i].l, lsh[++tot] = a[i].r;
    sort(lsh + 1, lsh + 1 + tot);
    tot = unique(lsh + 1, lsh + 1 + tot) - (lsh + 1);
    for(int i = 1; i <= n; i++) {
        a[i].l = lower_bound(lsh + 1, lsh + 1 + tot, a[i].l) - lsh;
        a[i].r = lower_bound(lsh + 1, lsh + 1 + tot, a[i].r) - lsh;
    }
    return ;
}
struct BIT {
    int sum[N];
    void update(int x, int w) {for(int i = x; i <= tot; sum[i] += w, i += (i & -i));}
    int query(int x) {int res = 0; for(int i = x; i; res += sum[i], i -= (i & -i)); return res;}
}T;
int f1[N << 1], f2[N];
int f1_nxt(int x) {return f1[x] == x ? x : f1[x] = f1_nxt(f1[x]);}
int f2_nxt(int x) {return f2[x] == x ? x : f2[x] = f2_nxt(f2[x]);}
struct Tree {
    int mn, pos, tg;
}nd[N << 2];
void mark(int k, int w) {nd[k].mn += w; nd[k].tg += w;}
void pushdown(int k) {
    if(nd[k].tg == 0)return ;
    mark(k << 1, nd[k].tg); mark(k << 1 | 1, nd[k].tg);
    nd[k].tg = 0;
    return ;
}
void pushup(int k) {
    Tree ls = nd[k << 1], rs = nd[k << 1 | 1];
    if((ls.mn < rs.mn) || (ls.mn == rs.mn && a[ls.pos].id < a[rs.pos].id))nd[k].mn = ls.mn, nd[k].pos = ls.pos;
    else nd[k].mn = rs.mn, nd[k].pos = rs.pos;
    return ;
}
void build(int k, int l, int r) {
    if(l == r)return nd[k].mn = INF, nd[k].pos = l, void();
    int mid = l + r >> 1;
    build(k << 1, l, mid); build(k << 1 | 1, mid + 1, r);
    pushup(k);
    return ;
}
void update(int k, int l, int r, int x, int w) {
    if(l == r)return nd[k].mn = w, void();
    int mid = l + r >> 1; pushdown(k);
    if(x <= mid)update(k << 1, l, mid, x, w);
    else update(k << 1 | 1, mid + 1, r, x, w);
    pushup(k);
    // printf("update:%d %d %d %lld %d\n", l, r, x, nd[k].mn, nd[k].pos);
    return ;
}
void add(int k, int l, int r, int qx, int qy, int w) {
    if(l >= qx && r <= qy)return mark(k, w), void();
    int mid = l + r >> 1; pushdown(k);
    if(qx <= mid)add(k << 1, l, mid, qx, qy, w);
    if(qy > mid)add(k << 1 | 1, mid + 1, r, qx, qy, w);
    pushup(k);
    return ;
}
signed main() { 
    n = read();
    for(int i = 1; i <= n; i++) {
        int l = read(), r = read(); 
        a[i] = Node(i, l, r);
    }
    disc(); sort(a + 1, a + 1 + n);
    build(1, 1, n);
    for(int i = 1; i <= tot; i++)T.update(i, lsh[i] - lsh[i - 1]);
    for(int i = 1; i <= tot + 1; i++)f1[i] = i;
    for(int i = 1; i <= n + 1; i++)f2[i] = i;
    set<pii> s1, s2;
    for(int i = 1, mx = 0; i <= n; i++) {
        if(mx < a[i].l) {
            update(1, 1, n, i, lsh[a[i].r] - lsh[a[i].l]);
            mx = a[i].l; f2[i] = f2_nxt(i + 1);
            s1.insert(mp(a[i].l, i)); s2.insert(mp(a[i].r, i));
            // cout << "init:" << i << ' ' << a[i].id << endl;
        }
    }
    vector<int> ans;
    while(ans.size() < n) {
        int pos = nd[1].pos; ans.pb(a[pos].id); 
        update(1, 1, n, pos, INF);
        // cerr << a[pos].id << endl;
        // cout << "pos:" << nd[1].pos << ' ' << nd[1].mn << endl;
        for(int i = a[pos].l + 1; i <= a[pos].r; i = f1_nxt(i + 1)) {
            T.update(i, -(lsh[i] - lsh[i - 1])); f1[i] = f1_nxt(i + 1);
            int l = (*s2.lower_bound(mp(i, 0))).SE, r = (*(--s1.upper_bound(mp(i - 1, INF)))).SE;
            // cout << i << ' ' << l << ' ' << r << endl;
            if(l <= r)add(1, 1, n, l, r, -(lsh[i] - lsh[i - 1]));
        }
        // cerr << pos << endl;
        s1.erase(mp(a[pos].l, pos)); s2.erase(mp(a[pos].r, pos));
        for(int i = f2_nxt(pos), mx = 0; i <= n; i = f2_nxt(i + 1)) {
            if(a[i].l <= mx || a[i].l > a[pos].l)break;
            auto now = s1.lower_bound(mp(a[i].l, 0));
            // cerr << "preins:" << i << ' ' << now << endl;
            // cerr << "ins:" << i << endl;
            if(now != s1.end() && a[(*now).SE].r <= a[i].r)break;
            s1.insert(mp(a[i].l, i)); s2.insert(mp(a[i].r, i)); f2[i] = f2_nxt(i + 1);
            update(1, 1, n, i, T.query(a[i].r) - T.query(a[i].l)); mx = a[i].l;
        }
    }
    for(int t : ans)printf("%lld ", t);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 9760kb

input:

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

output:

1 2 5 3 4 6 

result:

ok 6 tokens

Test #2:

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

input:

4
3 7
10 14
1 6
6 11

output:

1 3 2 4 

result:

ok 4 tokens

Test #3:

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

input:

100
50 51
49 51
49 52
48 52
48 53
47 53
47 54
46 54
46 55
45 55
45 56
44 56
44 57
43 57
43 58
42 58
42 59
41 59
41 60
40 60
40 61
39 61
39 62
38 62
38 63
37 63
37 64
36 64
36 65
35 65
35 66
34 66
34 67
33 67
33 68
32 68
32 69
31 69
31 70
30 70
30 71
29 71
29 72
28 72
28 73
27 73
27 74
26 74
26 75
25...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

result:

ok 100 tokens

Test #4:

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

input:

100
41 42
99 100
47 48
50 51
56 57
61 62
27 28
85 86
44 45
3 4
26 27
20 21
92 93
33 34
86 87
69 70
84 85
62 63
81 82
2 3
13 14
32 33
82 83
70 71
46 47
45 46
19 20
83 84
57 59
63 65
59 61
82 84
45 47
48 50
70 72
42 44
84 86
26 28
61 63
2 4
17 19
65 67
54 56
67 69
96 99
42 45
47 50
34 37
14 17
51 54
7...

output:

1 2 3 4 5 6 7 8 9 10 11 38 12 13 14 15 16 17 37 18 39 19 20 40 21 22 23 24 25 26 33 27 28 32 35 29 30 31 57 73 34 47 71 36 46 41 53 42 58 43 54 44 52 77 45 63 48 62 49 64 80 50 60 79 91 51 66 89 55 65 83 56 59 67 86 61 72 82 90 96 68 75 81 93 69 74 84 92 70 87 88 94 97 99 76 78 85 95 98 100 

result:

ok 100 tokens

Test #5:

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

input:

100
26 27
68 69
33 34
96 97
42 43
6 7
60 61
22 23
9 10
19 20
38 39
7 8
73 74
64 65
53 54
84 85
15 16
79 80
62 63
11 12
32 33
80 81
95 96
54 55
83 84
89 90
55 56
74 75
97 98
81 82
23 24
57 58
14 15
34 35
59 60
40 41
46 47
18 19
21 22
56 57
35 36
69 70
82 83
94 95
63 64
86 87
31 32
76 77
39 40
47 48
4...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

result:

ok 100 tokens

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 7780kb

input:

100
66 67
42 43
32 33
28 29
96 97
19 20
41 42
38 39
73 74
50 51
31 32
40 41
3 4
72 73
29 30
45 46
14 15
11 12
68 69
21 22
25 26
51 52
75 76
76 77
8 9
99 100
53 54
27 28
61 62
26 27
74 75
84 85
64 65
79 80
71 72
85 86
33 34
0 1
90 91
24 25
4 6
51 53
64 66
34 36
94 96
66 68
97 99
31 33
80 82
19 21
88 ...

output:

1 2 3 4 5 6 7 8 9 10 11 48 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 76 81 31 66 32 33 34 35 36 59 37 38 39 40 42 43 46 50 55 57 64 77 41 44 62 74 78 87 90 45 71 47 49 51 69 80 89 52 53 54 82 56 58 72 60 68 73 61 63 91 65 75 67 79 88 96 98 70 84 94 95 83 85 86 92 93 97 99 100 

result:

wrong answer 53rd words differ - expected: '41', found: '77'