oj.uz

Submission #282181

# Submission time Handle Problem Language Result Execution time Memory
282181 2020-08-24T05:55:35 Z 문홍윤(#5760) None (JOI15_walls) C++17
0 / 100
 102 ms 8304 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(f==nx[0]||ch[f]||ch[r])continue;
        assert(nx[f]==r&&pr[r]==f);
        assert(llabs(arr[f]-arr[r])==d);
        ch[f]=ch[r]=true;
        int pf=pr[f], nr=nx[r];
        nx[pf]=nr;
        pr[nr]=pf;
        if(!nr){
            cnt--;
            sum-=d;
            continue;
        }
        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=nx[0];
    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;
    nx[0]=1;
    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<=10){
            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=nx[0];
        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:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
walls.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         scanf("%lld %lld\n", &l[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |         scanf("%lld", &a);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 88 ms 7784 KB Output is correct
3 Correct 102 ms 8296 KB Output is correct
4 Correct 84 ms 8296 KB Output is correct
5 Correct 82 ms 8304 KB Output is correct
6 Incorrect 58 ms 8296 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 88 ms 7784 KB Output is correct
3 Correct 102 ms 8296 KB Output is correct
4 Correct 84 ms 8296 KB Output is correct
5 Correct 82 ms 8304 KB Output is correct
6 Incorrect 58 ms 8296 KB Output isn't correct
7 Halted 0 ms 0 KB -