QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#245644	#6392. Curtains	Chinese_zjc_	0	18ms	8480kb	C++14	2.7kb	2023-11-10 08:39:45	2023-11-10 08:39:46

Judging History

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

[2023-11-10 08:39:46]
评测

测评结果：0
用时：18ms
内存：8480kb

查看

[2023-11-10 08:39:45]
提交

answer

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
void cmax(int &A, int B) { A = std::max(A, B); }
void cmin(int &A, int B) { A = std::min(A, B); }
int n, m, q, l[500005], r[500005], ql[500005], qr[500005], v[500005], f[500005], g[500005];
bool ans[500005];
void solve(int L, int R, std::vector<int> A, std::vector<int> B)
{
    if (B.empty())
        return;
    int mid = (L + R) >> 1;
    std::vector<int> lA, rA, lB, rB;
    std::iota(f + L, f + R + 1, L);
    std::fill(g + L, g + mid, INT_MAX);
    std::fill(g + mid + 1, g + R + 1, INT_MIN);
    f[mid] = g[mid] = mid;
    for (auto i : A)
    {
        if (r[i] <= mid)
            cmax(f[l[i]], r[i]);
        if (mid <= l[i])
            cmin(f[r[i]], l[i]);
        if (l[i] <= mid && mid <= r[i])
        {
            cmin(g[l[i]], r[i]);
            cmax(g[r[i]], l[i]);
        }
    }
    std::vector<int> sta;
    for (int i = mid; i >= L; --i)
    {
        while (sta.size() >= 2 && sta.end()[-2] <= f[i])
            sta.pop_back();
        if (sta.size() && sta.back() <= f[i])
            cmin(g[i], g[sta.back()]);
        while (sta.size() && g[sta.back()] >= g[i])
            sta.pop_back();
        sta.push_back(i);
    }
    sta.clear();
    for (int i = mid; i <= R; ++i)
    {
        while (sta.size() >= 2 && f[i] <= sta.end()[-2])
            sta.pop_back();
        if (sta.size() && f[i] <= sta.back())
            cmin(g[i], g[sta.back()]);
        while (sta.size() && g[sta.back()] <= g[i])
            sta.pop_back();
        sta.push_back(i);
    }
    // std::cout << L << ' ' << R << ' ' << A.size() << ' ' << B.size() << std::endl;
    // for (int i = L; i <= R; ++i)
    //     std::cout << g[i] << " \n"[i == R];
    sta.clear();
    for (auto i : A)
        if (r[i] < mid)
            lA.push_back(i);
        else if (mid < l[i])
            rA.push_back(i);
    for (auto i : B)
        if (qr[i] < mid)
            lB.push_back(i);
        else if (mid < ql[i])
            rB.push_back(i);
        else
            ans[i] = g[ql[i]] <= qr[i] && ql[i] <= g[qr[i]];
    solve(L, mid - 1, lA, lB);
    solve(mid + 1, R, rA, rB);
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> m >> q;
    std::vector<int> a(m), b(q);
    std::iota(a.begin(), a.end(), 0);
    std::iota(b.begin(), b.end(), 0);
    for (int i = 0; i != m; ++i)
        std::cin >> l[i] >> r[i], --l[i];
    for (int i = 0; i != q; ++i)
        std::cin >> ql[i] >> qr[i], --ql[i];
    solve(0, n, a, b);
    for (int i = 0; i != q; ++i)
        std::cout << (ans[i] ? "YES" : "NO") << '\n';
    return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 3480kb

input:

200 200 200
113 134
77 77
110 143
126 157
122 131
161 172
59 134
19 68
117 142
15 103
61 182
12 67
73 97
72 128
68 110
19 137
14 118
60 150
42 64
25 30
118 158
149 164
79 149
21 94
33 82
3 130
36 142
57 170
64 140
40 98
115 132
2 45
27 85
43 181
120 125
82 160
121 176
16 154
59 74
34 52
71 74
57 185...

output:

NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
YES
NO
NO
N...

result:

wrong answer 2nd lines differ - expected: 'YES', found: 'NO'

Subtask #2:

score: 0

Skipped

Dependency #1:

Subtask #3:

score: 0

Skipped

Dependency #2:

Subtask #4:

score: 0

Wrong Answer

Test #32:

score: 0

Wrong Answer

time: 18ms

memory: 8480kb

input:

100000 100000 100000
44237 85021
45776 80409
39632 94735
28119 63770
47399 73347
28902 87358
27924 65499
23898 54817
50114 96633
11325 37690
46642 94643
9271 47594
47324 47948
27957 58134
20443 88720
20834 89483
77577 94705
7835 30030
37387 59648
8364 76478
66145 76025
12683 79475
1745 33181
43966 5...

output:

YES
NO
NO
NO
NO
YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
YES
YES
NO
NO
NO
NO
YES
YES
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
YES
NO
YES
NO
YES
NO
...

result:

wrong answer 3rd lines differ - expected: 'YES', found: 'NO'

Subtask #5:

score: 0

Skipped

Dependency #3:

Subtask #6:

score: 0

Skipped