QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#528108 | #2774. Scenery | ship2077 | WA | 1ms | 7804kb | C++14 | 2.2kb | 2024-08-23 08:58:59 | 2024-08-23 08:58:59 |
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];vector<int>pos[M];
int p[M],f[M],siz[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]);}
void merge(int x,int y){
if (siz[x]>siz[y]) swap(x,y);
f[x]=y;siz[y]+=siz[x];
}
bool Bellman_Ford(){
for (int i=2;i<=N;i++) dis[i]=1ll<<60;
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,siz[p[i]]=p[i]-p[i-1];
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]){
const int pr=find(pre[x]);
if (dis[pr]<dis[x]-lazy[x]) break;
lazy[x]+=lazy[pr];merge(pr,x);pre[x]=pre[pr];
}
}
int x=find(i+1);
flag|=chkmin(dis[i],dis[x]-lazy[x]);
}
if (!flag) return 1;
if (dis[1]<0) return 0;
}
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: 0ms
memory: 7744kb
input:
2 10 0 15 5 20
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 7680kb
input:
2 10 1 15 0 20
output:
no
result:
ok single line: 'no'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7804kb
input:
2 10 5 30 10 20
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7704kb
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: -100
Wrong Answer
time: 0ms
memory: 7740kb
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:
yes
result:
wrong answer 1st lines differ - expected: 'no', found: 'yes'