Submission #677436

#	Time	Username	Problem	Language	Result	Execution time	Memory
677436		qwerasdfzxcl	방벽 (JOI15_walls)	C++17	100 / 100	291 ms	38056 KiB

walls

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr ll INF = 1e18;
constexpr int INF2 = 1e9 + 100;
ll a[200200];
int l[200200], r[200200], n, q;

pair<ll, int> operator + (const pair<ll, int> &x, const pair<ll, int> &y) {return make_pair(x.first + y.first, x.second + y.second);}
pair<ll, int> operator - (const pair<ll, int> &x, const pair<ll, int> &y) {return make_pair(x.first - y.first, x.second - y.second);}
ll myabs(ll x){return x<0?-x:x;}

struct Edge{
    int s, e;
    ll x;
    Edge(){}
    Edge(int _s, int _e, ll _x): s(_s), e(_e), x(_x) {}
    bool operator < (const Edge &E) const{
        return tie(x, s) > tie(E.x, E.s);
    }
};

struct Linked_List{
    int nxt[200200], prv[200200];
    pair<ll, int> dist[200200], T; ///dist[i] = (i -> nxt[i])
    priority_queue<Edge> pq;
    ll a[200200];

    void ch(int i, ll x, int y){
        T = T - dist[i];
        dist[i] = {x, y};
        T = T + dist[i];
    }

    void init(ll s){
        //printf(" a[0] = %lld\n", s);
        for (int i=1;i<=n;i++) a[i] = ::a[i];
        a[0] = s;
        fill(nxt, nxt+n+1, -INF2);
        fill(prv, prv+n+1, -INF2);
        fill(dist, dist+n+1, make_pair(0LL, 0));

        for (int i=0;i<n;){
            int j = i+1;
            ll dmn = a[j] - a[i], dmx = a[j] - a[i];
            while(j<=n){
                dmn = min(dmn, a[j] - a[j-1]);
                dmx = max(dmx, a[j] - a[j-1]);
                if (dmn < 0 && dmx > 0) break;
                j++;
            }

            if (dmn==0 && dmx==0) break;
            --j;

            //printf(" i = %d / j = %d\n", i, j);

            nxt[i] = j, prv[j] = i;
            if (i){
                ch(i, myabs(a[j]-a[i]), 1);
                pq.emplace(i, j, dist[i].first);
            }

            i = j;
        }
    }

    void process(int L){
        while(!pq.empty()){
            auto [s, e, x] = pq.top();
            if (x>L) break;
            pq.pop();

            if (nxt[s]!=e) continue;

            int ss = prv[s], ee = nxt[e];

            ///delete
            nxt[s] = -INF2;
            prv[e] = -INF2;
            ch(s, 0, 0);

            ///link
            assert(ss!=-INF2);
            if (ee==-INF2) continue;

            prv[s] = -INF2;
            nxt[e] = -INF2;
            ch(e, 0, 0);

            nxt[ss] = ee, prv[ee] = ss;
            if (ss){
                ch(ss, myabs(a[ee]-a[ss]), 1);
                pq.emplace(ss, ee, dist[ss].first);
            }
        }
    }

    ll query(int s, int L, int x){
        process(L);
        auto [sum, c] = T;
        return sum - (ll)L*c + myabs(x - a[nxt[0]]);
    }
}Llist, Rlist;

ll pmn[200200], pmx[200200], pL[200200], pR[200200], iL[200200], iR[200200], ans[200200];

ll calc(int L, int R){
    int posL = upper_bound(pmn+1, pmn+n+1, -L) - pmn;
    int posR = upper_bound(pmx+1, pmx+n+1, R) - pmx;
    if (posL==n+1 && posR==n+1) return 0;

    if (posL < posR){
        int pos = upper_bound(pL+1, pL+n+1, R-L) - pL - 1;
        return Rlist.query(iL[pos], R-L, L);
    }
    else{
        assert(posL > posR);
        int pos = upper_bound(pR+1, pR+n+1, R-L) - pR - 1;
        return Llist.query(iR[pos], R-L, R);
    }

    assert(0);
    return 0;
}

bool cmp(int i, int j){return r[i] - l[i] < r[j] - l[j];}

int main(){
    scanf("%d %d", &q, &n);
    for (int i=1;i<=q;i++) scanf("%d %d", l+i, r+i);
    for (int i=1;i<=n;i++) scanf("%lld", a+i);

    Llist.init(-INF);
    Rlist.init(INF);

    pmn[0] = -INF2, pmx[0] = -INF2, pL[0] = -INF2, pR[0] = -INF2;
    for (int i=1;i<=n;i++){
        if (pmn[i-1] < -a[i]) iL[i] = i;
        else iL[i] = iL[i-1];
        if (pmx[i-1] < a[i]) iR[i] = i;
        else iR[i] = iR[i-1];

        pmn[i] = max(pmn[i-1], -a[i]);
        pmx[i] = max(pmx[i-1], a[i]);
        pL[i] = max(pL[i-1], a[i] + pmn[i]);
        pR[i] = max(pR[i-1], pmx[i] - a[i]);
    }

    vector<int> idx;
    for (int i=1;i<=q;i++) idx.push_back(i);
    sort(idx.begin(), idx.end(), cmp);

    for (auto &i:idx) ans[i] = calc(l[i], r[i]);
    for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);
    return 0;
}

Compilation message (stderr)

walls.cpp: In function 'int main()':
walls.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     scanf("%d %d", &q, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
walls.cpp:132:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     for (int i=1;i<=q;i++) scanf("%d %d", l+i, r+i);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~
walls.cpp:133:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                            ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 45 / 45
• Subtask 3: 45 / 45