QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#345265	#6392. Curtains	ship2077	0	40ms	43656kb	C++14	1.4kb	2024-03-06 18:42:52	2024-03-06 18:42:52

Judging History

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

[2024-03-06 18:42:52]
评测

测评结果：0
用时：40ms
内存：43656kb

查看

[2024-03-06 18:42:52]
提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int M=5e5+5;
vector<int>upd1[M],upd2[M];
vector<pair<int,int>>qry[M];
int n,m,q,l,r,f[M],g[M],stk[M];
bool ans[M];
int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
void solve(int l,int r){
    if (l>=r) return ;
    int mid=l+r>>1;
    for (int i=mid,tp=0;i>=l;i--){
        f[i]=0x3f3f3f3f;
        for (auto j:upd1[i])
            if (j>mid) f[i]=min(f[i],j);
            else while (tp&&stk[tp]<=j)
                f[i]=min(f[i],f[stk[tp--]]);
        stk[++tp]=i;
    }
    for (int i=mid+1,tp=0;i<=r;i++){
        g[i]=0;
        for (auto j:upd2[i])
            if (j<=mid) g[i]=max(g[i],j);
            else while (tp&&stk[tp]>=j)
                g[i]=min(g[i],g[stk[tp--]]);
        stk[++tp]=i;
    }
    for (int i=l;i<=mid;i++)
        for (auto [j,k]:qry[i])
            if (j>mid)
                ans[k]=f[i]<=j&&g[j]>=i;
    solve(l,mid);solve(mid+1,r);
}
int main(){
    n=read()+1;m=read();q=read();
    for (int i=1;i<=m;i++){
        l=read();r=read()+1;
        upd1[l].push_back(r);
        upd2[r].push_back(l);
    }
    for (int i=1;i<=q;i++){
        l=read();r=read()+1;
        qry[l].push_back({r,i});
    }
    solve(1,n);
    for (int i=1;i<=q;i++)
        puts(ans[i]?"YES":"NO");
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 3ms

memory: 38808kb

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
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
YES
NO
NO
NO
...

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: 40ms

memory: 43656kb

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
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
YES
YES
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
NO
NO
YES
NO
YES
YES
NO
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
YES
NO
NO
NO
N...

result:

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

Subtask #5:

score: 0

Skipped

Dependency #3:

Subtask #6:

score: 0

Skipped