QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#528108#2774. Sceneryship2077WA 1ms7804kbC++142.2kb2024-08-23 08:58:592024-08-23 08:58:59

Judging History

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

  • [2024-08-23 08:58:59]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7804kb
  • [2024-08-23 08:58:59]
  • 提交

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'