QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#528105#2774. Sceneryship2077TL 3063ms10204kbC++141.9kb2024-08-23 08:49:212024-08-23 08:49:21

Judging History

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

  • [2024-08-23 08:49:21]
  • 评测
  • 测评结果:TL
  • 用时:3063ms
  • 内存:10204kb
  • [2024-08-23 08:49:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int M=1e5+5;
int n,t,N,num,a[M],b[M],lsh[M];
long long dis[M],tree[M];
vector<int>pos[M];
int p[M],f[M],pre[M],lazy[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;
}
bool chkmin(long long &x,long long y){return x>y?x=y,1:0;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
bool Bellman_Ford(){
    for (int i=1;i<=N;i++){ bool flag=0;
        long long rec=dis[1]-lsh[1]/t,tmp=lsh[1]%t;
        for (int i=2;i<=N;i++){
            flag|=chkmin(dis[i],lsh[i]/t+rec+(lsh[i]%t>tmp));
            long long Rec=dis[i]-lsh[i]/t,Tmp=lsh[i]%t;
            if (Rec==rec&&tmp<Tmp||Rec<rec) rec=Rec,tmp=Tmp;
        }
        p[num=1]=N;
        for (int i=N-1;i;i--)
            if (dis[i]<dis[p[num]])
                p[++num]=i;
        reverse(p+1,p+num+1);
        for (int i=1;i<=num;i++) pre[p[i]]=p[i-1],lazy[p[i]]=0;
        for (int i=1;i<=num;i++)
            for (int j=p[i-1]+1;j<=p[i];j++)
                f[j]=p[i];
        for (int i=N-1;i;i--){
            for (auto j:pos[i]){
                int x=find(j); lazy[x]++;
                while (pre[x]&&dis[pre[x]]>dis[x]-lazy[x])
                    lazy[x]+=lazy[pre[x]],f[find(pre[x])]=find(x),pre[x]=pre[pre[x]];
            }
            int x=find(i+1);
            flag|=chkmin(dis[i],dis[x]-lazy[x]);
        }
        if (!flag) return 1;
    }
    return 0;
}
int main(){
    n=read();t=read();
    for (int i=1;i<=n;i++)
        a[i]=read()-1,b[i]=read()-t,
        lsh[++N]=a[i],lsh[++N]=b[i];
    sort(lsh+1,lsh+N+1);N=unique(lsh+1,lsh+N+1)-lsh-1;
    for (int i=1;i<=n;i++)
        a[i]=lower_bound(lsh+1,lsh+N+1,a[i])-lsh,
        b[i]=lower_bound(lsh+1,lsh+N+1,b[i])-lsh,
        pos[a[i]].emplace_back(b[i]);
    puts(Bellman_Ford()?"yes":"no");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7864kb

input:

2 10
0 15
5 20

output:

yes

result:

ok single line: 'yes'

Test #2:

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

input:

2 10
1 15
0 20

output:

no

result:

ok single line: 'no'

Test #3:

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

input:

2 10
5 30
10 20

output:

yes

result:

ok single line: 'yes'

Test #4:

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

input:

11 6
0 74
2 60
4 34
10 36
21 46
26 40
28 38
30 48
50 68
52 68
54 62

output:

yes

result:

ok single line: 'yes'

Test #5:

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

input:

11 6
0 74
2 60
4 34
10 36
21 46
26 40
28 38
30 48
50 68
52 67
54 62

output:

no

result:

ok single line: 'no'

Test #6:

score: 0
Accepted
time: 469ms
memory: 8344kb

input:

9695 10
1 146
0 68
1 30
10 20
39 68
48 58
77 145
78 107
88 98
116 145
125 135
147 292
146 214
147 176
157 167
185 214
194 204
223 291
224 253
233 243
262 291
271 281
293 438
292 360
293 322
303 313
331 360
341 351
369 437
370 399
380 390
408 437
418 428
439 584
438 506
439 468
448 458
477 506
487 49...

output:

yes

result:

ok single line: 'yes'

Test #7:

score: 0
Accepted
time: 3063ms
memory: 8616kb

input:

9696 10
1 146
0 68
1 30
10 20
39 68
48 58
77 145
78 107
88 98
116 145
125 135
147 292
146 214
147 176
157 167
185 214
194 204
223 291
224 253
233 243
262 291
271 281
293 438
292 360
293 322
303 313
331 360
341 351
369 437
370 399
380 390
408 437
418 428
439 584
438 506
439 468
448 458
477 506
487 49...

output:

no

result:

ok single line: 'no'

Test #8:

score: 0
Accepted
time: 0ms
memory: 9880kb

input:

2 42
10 90
10 90

output:

no

result:

ok single line: 'no'

Test #9:

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

input:

2 42
6 90
6 90

output:

yes

result:

ok single line: 'yes'

Test #10:

score: 0
Accepted
time: 0ms
memory: 9856kb

input:

3 1
0 2
0 1
0 2

output:

no

result:

ok single line: 'no'

Test #11:

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

input:

3 1
0 1000000000
0 1
0 2

output:

yes

result:

ok single line: 'yes'

Test #12:

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

input:

5 5
0 29
1 24
3 14
2 19
4 9

output:

yes

result:

ok single line: 'yes'

Test #13:

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

input:

5 5
3 15
1 25
4 10
2 20
0 28

output:

yes

result:

ok single line: 'yes'

Test #14:

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

input:

5 5
2 19
3 14
0 28
4 9
1 24

output:

no

result:

ok single line: 'no'

Test #15:

score: 0
Accepted
time: 0ms
memory: 7700kb

input:

5 10
31 41
1 11
11 21
21 31
41 51

output:

yes

result:

ok single line: 'yes'

Test #16:

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

input:

5 10
11 21
32 43
1 11
41 51
21 31

output:

no

result:

ok single line: 'no'

Test #17:

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

input:

10 2
9 11
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20

output:

no

result:

ok single line: 'no'

Test #18:

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

input:

10 2
10 12
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20
0 20

output:

yes

result:

ok single line: 'yes'

Test #19:

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

input:

11 3
12 15
17 20
1 38
2 38
3 35
4 33
5 32
6 29
7 27
8 26
9 23

output:

yes

result:

ok single line: 'yes'

Test #20:

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

input:

11 3
12 15
17 20
1 37
2 37
3 35
4 33
5 32
6 29
7 27
8 26
9 23

output:

no

result:

ok single line: 'no'

Test #21:

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

input:

11 3
12 15
17 20
1 38
2 35
3 32
4 32
5 29
6 27
7 26
8 23
9 21

output:

yes

result:

ok single line: 'yes'

Test #22:

score: 0
Accepted
time: 0ms
memory: 9736kb

input:

11 3
12 15
17 20
1 37
2 35
3 32
4 32
5 29
6 27
7 26
8 23
9 21

output:

no

result:

ok single line: 'no'

Test #23:

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

input:

1 42
9 52

output:

yes

result:

ok single line: 'yes'

Test #24:

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

input:

1 42
11 53

output:

yes

result:

ok single line: 'yes'

Test #25:

score: 0
Accepted
time: 0ms
memory: 7760kb

input:

11 6
12 20
6 22
6 24
26 44
36 46
34 48
28 53
38 64
40 70
14 72
0 74

output:

yes

result:

ok single line: 'yes'

Test #26:

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

input:

11 6
12 20
7 22
6 24
26 44
36 46
34 48
28 53
38 64
40 70
14 72
0 74

output:

no

result:

ok single line: 'no'

Test #27:

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

input:

1000 10
2531 2541
7171 7181
8601 8611
5681 5691
8271 8281
6031 6041
7481 7491
7141 7151
2841 2851
9651 9661
901 911
8101 8111
4581 4591
781 791
9481 9491
1351 1361
4211 4221
8631 8641
7611 7621
2811 2821
7561 7571
2341 2351
3511 3521
2161 2171
931 941
2361 2371
3261 3271
7471 7481
7591 7601
9701 971...

output:

yes

result:

ok single line: 'yes'

Test #28:

score: 0
Accepted
time: 33ms
memory: 8208kb

input:

1000 10
5391 5401
8741 8751
4491 4501
771 781
4081 4091
4981 4991
8631 8641
7921 7931
8601 8611
4671 4681
671 681
3601 3611
9671 9681
7241 7251
31 41
7471 7481
6981 6991
9581 9591
9521 9531
311 321
571 581
5651 5661
8121 8131
2121 2131
9051 9061
4051 4061
411 421
5851 5861
3421 3431
2181 2191
301 31...

output:

no

result:

ok single line: 'no'

Test #29:

score: 0
Accepted
time: 0ms
memory: 8248kb

input:

9998 100000
0 100000
100000 200000
200000 300000
300000 400000
400000 500000
500000 600000
600000 700000
700000 800000
800000 900000
900000 1000000
1000000 1100000
1100000 1200000
1200000 1300000
1300000 1400000
1400000 1500000
1500000 1600000
1600000 1700000
1700000 1800000
1800000 1900000
1900000 ...

output:

yes

result:

ok single line: 'yes'

Test #30:

score: 0
Accepted
time: 0ms
memory: 8452kb

input:

9998 100000
0 500090002
1 500090003
2 500090004
3 500090005
4 500090006
5 500090007
6 500090008
7 500090009
8 500090010
9 500090011
10 500090012
11 500090013
12 500090014
13 500090015
14 500090016
15 500090017
16 500090018
17 500090019
18 500090020
19 500090021
20 500090022
21 500090023
22 500090024...

output:

yes

result:

ok single line: 'yes'

Test #31:

score: 0
Accepted
time: 2ms
memory: 9820kb

input:

9999 2
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998
0 9998...

output:

yes

result:

ok single line: 'yes'

Test #32:

score: 0
Accepted
time: 551ms
memory: 10060kb

input:

9999 2
0 24998
3 5
0 24998
8 10
0 24998
13 15
0 24998
18 20
0 24998
23 25
0 24998
28 30
0 24998
33 35
0 24998
38 40
0 24998
43 45
0 24998
48 50
0 24998
53 55
0 24998
58 60
0 24998
63 65
0 24998
68 70
0 24998
73 75
0 24998
78 80
0 24998
83 85
0 24998
88 90
0 24998
93 95
0 24998
98 100
0 24998
103 105...

output:

yes

result:

ok single line: 'yes'

Test #33:

score: 0
Accepted
time: 174ms
memory: 8172kb

input:

9998 2
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998
0 4998...

output:

yes

result:

ok single line: 'yes'

Test #34:

score: 0
Accepted
time: 2ms
memory: 8272kb

input:

1000 100000
234294286 234427116
161692120 161858166
192115615 192281661
249806722 249914914
151576139 151708909
114641576 114757960
104548340 104713878
164209630 164310142
157794261 157894325
162645705 162782567
246941564 247041566
239320500 239420503
114930600 115163718
242154008 242254022
16044404...

output:

yes

result:

ok single line: 'yes'

Test #35:

score: 0
Accepted
time: 2ms
memory: 9992kb

input:

10000 2
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20000
0 20...

output:

yes

result:

ok single line: 'yes'

Test #36:

score: 0
Accepted
time: 4ms
memory: 8072kb

input:

10000 2
0 17555
0 19254
0 15037
0 18199
0 11173
0 10572
0 18184
0 15762
0 17553
0 11675
0 13815
0 19695
0 15674
0 12854
0 19852
0 16035
0 15579
0 12043
0 15226
0 19883
0 14158
0 18568
0 12265
0 17070
0 18408
0 13094
0 15787
0 18251
1215 1219
0 12175
0 10628
0 13125
0 17721
0 16106
0 12383
0 14188
0 ...

output:

yes

result:

ok single line: 'yes'

Test #37:

score: 0
Accepted
time: 2270ms
memory: 8180kb

input:

10000 2
0 12749
0 12156
0 12589
0 15646
0 17003
0 11243
0 14684
0 17499
0 11267
0 11779
0 18800
0 13045
0 16460
0 18119
0 16146
3110 3114
0 13235
0 19449
0 14430
0 17160
0 19845
4245 4249
0 17029
0 18804
0 15165
0 16667
0 19672
0 14830
0 13756
0 13679
0 16430
0 12714
0 13757
0 16290
0 18071
0 12074
...

output:

no

result:

ok single line: 'no'

Test #38:

score: 0
Accepted
time: 7ms
memory: 10204kb

input:

10000 1000
17837225 17838736
13835975 13837485
10147097 10148191
16541494 16546596
22964403 22969753
24876001 24877017
16970577 16980791
13614888 13620046
20608929 20634503
11601939 11603005
22725453 22726484
17440772 17445994
12747736 12749886
19430111 19431112
12502813 12507915
18530376 18537518
1...

output:

yes

result:

ok single line: 'yes'

Test #39:

score: 0
Accepted
time: 2ms
memory: 8380kb

input:

10000 10000
56933425 57126261
56912552 57110895
56909805 57109504
56918462 57108860
56933012 57117951
76156016 76408259
76164566 76408515
76169547 76398813
76165933 76422619
76156961 76410693
31273183 31423711
31274071 31443006
31295851 31433414
31290019 31445862
31271894 31436748
124134097 12428280...

output:

yes

result:

ok single line: 'yes'

Test #40:

score: -100
Time Limit Exceeded

input:

10000 10000
2077289 2271938
2066887 2264909
2079933 2277871
2057852 2258918
2079173 2262030
140653393 140757341
140650251 140762746
140649667 140753296
140646497 140754025
140645838 140769611
63566316 63828615
63569276 63813477
63565213 63825681
63574900 63827490
63574016 63835497
166313963 16641066...

output:


result: