Submission #282188

# Submission time Handle Problem Language Result Execution time Memory
282188 2020-08-24T06:12:41 Z 문홍윤(#5760) None (JOI15_walls) C++17
0 / 100
99 ms 6608 KB
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, int> pli;

int n, m, re;
LL l[200010], r[200010], arr[200010]={-1}, ans[200010];
vector<pli> vc;

priority_queue<pair<LL, pii>, vector<pair<LL, pii> >, greater<pair<LL, pii> > > pq;
int pr[200010], nx[200010];
LL sum, cnt;
bool ch[200010];

void calc_pq(LL num){
    while(pq.size()){
        LL d=pq.top().F;
        int f=pq.top().S.F, r=pq.top().S.S;
        if(d>=num)return;
        pq.pop();
        if(ch[f]||ch[r])continue;
        ch[f]=ch[r]=true;
        int pf=pr[f], nr=nx[r];
        if(!nr){
            nx[f]=0;
            cnt--;
            sum-=d;
            continue;
        }
        if(!pf){
            nx[f]=nr;
            pr[nr]=f;
            cnt--;
            sum-=llabs(arr[r]-arr[f]);
            sum-=llabs(arr[nr]-arr[r]);
            sum+=llabs(arr[nr]-arr[f]);
            pq.push(mp(llabs(arr[nr]-arr[f]), mp(f, nr)));
            continue;
        }
        nx[pf]=nr;
        pr[nr]=pf;
        cnt-=2;
        sum-=llabs(arr[f]-arr[pf]);
        sum-=llabs(arr[r]-arr[f]);
        sum-=llabs(arr[nr]-arr[r]);
        sum+=llabs(arr[nr]-arr[pf]);
        pq.push(mp(llabs(arr[nr]-arr[pf]), mp(pf, nr)));
    }
}

void get_naive(int num){
    int nw=1;
    LL nl=l[num], nr=r[num];
    while(nw){
        if(nr<=arr[nw]){
            ans[num]+=arr[nw]-nr;
            nl+=arr[nw]-nr;
            nr=arr[nw];
        }
        if(arr[nw]<=nl){
            ans[num]+=nl-arr[nw];
            nr-=nl-arr[nw];
            nl=arr[nw];
        }
        nw=nx[nw];
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld\n", &l[i], &r[i]);
        vc.eb(r[i]-l[i], i);
    }
    svec(vc);
    for(int i=1; i<=m; i++){
        LL a;
        scanf("%lld", &a);
        if(arr[re]==a)continue;
        if(re<2){
            arr[++re]=a;
            continue;
        }
        if(arr[re]-arr[re-1]<0&&a-arr[re]<0){
            arr[re]=a;
            continue;
        }
        if(arr[re]-arr[re-1]>0&&a-arr[re]>0){
            arr[re]=a;
            continue;
        }
        arr[++re]=a;
    }
    m=re;
    for(int i=2; i<=m; i++){
        pq.push(mp(llabs(arr[i]-arr[i-1]), mp(i-1, i)));
        sum+=llabs(arr[i]-arr[i-1]);
        cnt++;
        nx[i-1]=i;
        pr[i]=i-1;
    }
    for(auto i:vc){
        if(cnt<=20){
            get_naive(i.S);
            continue;
        }
        calc_pq(i.F);
        ans[i.S]=sum-cnt*i.F;
        LL nl=l[i.S], nr=r[i.S];
        int fr=1;
        if(nr<=arr[fr]){
            ans[i.S]+=arr[fr]-nr;
            nl+=arr[fr]-nr;
            nr=arr[fr];
        }
        if(arr[fr]<=nl){
            ans[i.S]+=nl-arr[fr];
            nr-=nl-arr[fr];
            nl=arr[fr];
        }
        for(int t=1; t<=3; t++){
            if(nx[fr]){
                ans[i.S]-=llabs(arr[fr]-arr[nx[fr]])-i.F;
                fr=nx[fr];
                if(nr<=arr[fr]){
                    ans[i.S]+=arr[fr]-nr;
                    nl+=arr[fr]-nr;
                    nr=arr[fr];
                }
                if(arr[fr]<=nl){
                    ans[i.S]+=nl-arr[fr];
                    nr-=nl-arr[fr];
                    nl=arr[fr];
                }
            }
        }
    }
    for(int i=1; i<=n; i++)printf("%lld\n", ans[i]);
}

Compilation message

walls.cpp: In function 'int main()':
walls.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
walls.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         scanf("%lld %lld\n", &l[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         scanf("%lld", &a);
      |         ~~~~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 664 KB Output is correct
2 Incorrect 99 ms 6608 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 664 KB Output is correct
2 Incorrect 99 ms 6608 KB Output isn't correct
3 Halted 0 ms 0 KB -