QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#527877 | #2774. Scenery | ship2077 | RE | 0ms | 3752kb | C++14 | 1.3kb | 2024-08-22 21:26:45 | 2024-08-22 21:26:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int M=2005;
int n,t,N,a[M],b[M],lsh[M];
int dis[M],sum[M][M];
vector<tuple<int,int,int>>edge;
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;
}
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;
auto link=[&](auto u,auto v,auto w){
edge.emplace_back(u,v,w);
};
for (int i=1;i<=N;i++)
for (int j=i+1;j<=N;j++)
link(i,j,(lsh[j]-lsh[i]+t-1)/t);
for (int i=1;i<=n;i++)
for (int j=1;j<=a[i];j++)
for (int k=b[i];k<=N;k++)
sum[j][k]++;
for (int i=1;i<=N;i++)
for (int j=i+1;j<=N;j++)
link(j,i,-sum[i][j]);
for (int i=1;i<N;i++)
for (auto [x,y,z]:edge)
if (dis[x]+z<dis[y])
dis[y]=dis[x]+z;
for (auto [x,y,z]:edge)
if (dis[x]+z<dis[y])
return puts("no"),0;
return puts("yes"),0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
2 10 0 15 5 20
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
2 10 1 15 0 20
output:
no
result:
ok single line: 'no'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
2 10 5 30 10 20
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3752kb
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: 0ms
memory: 3720kb
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: -100
Runtime Error
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...