Submission #677435

#	Time	Username	Problem	Language	Result	Execution time	Memory
677435		qwerasdfzxcl	방벽 (JOI15_walls)	C++17	100 / 100	412 ms	56984 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);}
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 Seg{
    pair<ll, int> tree[400400];
    ll treemin[400400];
    int sz;
    void init(int n, pair<ll, int> a[]){
        sz = n;
        for (int i=sz;i<sz*2;i++){
            tree[i] = a[i-sz];
            if (a[i-sz].second > 0) treemin[i] = a[i-sz].first;
            else treemin[i] = INF2;
        }
        for (int i=sz-1;i;i--){
            tree[i] = tree[i<<1] + tree[i<<1|1];
            treemin[i] = std::min(treemin[i<<1], treemin[i<<1|1]);
        }
    }
    void update(int p, pair<ll, int> x){
        p += sz;
        if (x.second > 0) treemin[p] = x.first;
        else treemin[p] = INF2;
        tree[p] = x;
        for (p>>=1;p;p>>=1){
            tree[p] = tree[p<<1] + tree[p<<1|1];
            treemin[p] = std::min(treemin[p<<1], treemin[p<<1|1]);
        }
    }
    pair<ll, int> query(int l, int r){
        pair<ll, int> ret = make_pair(0LL, 0);
        ++r;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = ret + tree[l++];
            if (r&1) ret = ret + tree[--r];
        }
        return ret;
    }
    ll min(){return treemin[1];}
};

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

    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;
            dist[i] = make_pair(myabs(a[j] - a[i]), 1);
            pq.emplace(i, j, dist[i].first);

            i = j;
        }

        tree.init(n+1, dist);
    }

    void process(int L){
        while(tree.min() <= L){
            auto [s, e, x] = pq.top(); pq.pop();
            if (nxt[s]!=e) continue;
            //printf("delete: %d %d %lld\n", s, e, x);

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

            ///delete
            nxt[s] = -INF2;
            prv[e] = -INF2;
            dist[s] = make_pair(0LL, 0);
            tree.update(s, dist[s]);

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

            prv[s] = -INF2;
            nxt[e] = -INF2;
            dist[e] = make_pair(0LL, 0);
            tree.update(e, dist[e]);

            nxt[ss] = ee, prv[ee] = ss;
            dist[ss] = make_pair(myabs(a[ee]-a[ss]), 1);
            tree.update(ss, dist[ss]);
            pq.emplace(ss, ee, dist[ss].first);
        }
    }

    ll query(int s, int L, int x){
        //printf("query %d %d (%lld)\n", L, s, a[0]);
        process(L);
        auto [sum, c] = tree.query(1, n);
        //printf(" sum = %lld / c = %d -> %lld\n", sum, c, sum - (ll)(L)*c);
        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:164:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |     scanf("%d %d", &q, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
walls.cpp:165:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |     for (int i=1;i<=q;i++) scanf("%d %d", l+i, r+i);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~
walls.cpp:166:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                            ~~~~~^~~~~~~~~~~~~

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