QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#528105 | #2774. Scenery | ship2077 | TL | 3063ms | 10204kb | C++14 | 1.9kb | 2024-08-23 08:49:21 | 2024-08-23 08:49:21 |
Judging History
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...