oj.uz

답안 #677430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677430 2023-01-03T10:03:07 Z qwerasdfzxcl 방벽 (JOI15_walls) C++17
100 / 100
 415 ms 62640 KB 
#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){
        //printf("query %d %d (%lld)\n", L, s, a[0]);
        process(L);
        auto [sum, c] = tree.query(s, n);
        //printf(" sum = %lld / c = %d -> %lld\n", sum, c, sum - (ll)(L)*c);
        return sum - (ll)(L)*c;
    }
}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 - a[iL[pos]]);
    }
    else{
        assert(posL > posR);
        int pos = upper_bound(pR+1, pR+n+1, R-L) - pR - 1;
        return Llist.query(iR[pos], R-L) + (a[iR[pos]] - 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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 20820 KB Output is correct
2 Correct 96 ms 47300 KB Output is correct
3 Correct 108 ms 49504 KB Output is correct
4 Correct 88 ms 49348 KB Output is correct
5 Correct 93 ms 49412 KB Output is correct
6 Correct 67 ms 49432 KB Output is correct
7 Correct 60 ms 42916 KB Output is correct
8 Correct 41 ms 42888 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 23192 KB Output is correct
2 Correct 128 ms 49772 KB Output is correct
3 Correct 127 ms 31176 KB Output is correct
4 Correct 259 ms 60956 KB Output is correct
5 Correct 225 ms 58796 KB Output is correct
6 Correct 262 ms 60864 KB Output is correct
7 Correct 226 ms 58800 KB Output is correct
8 Correct 256 ms 60864 KB Output is correct
9 Correct 119 ms 51672 KB Output is correct
10 Correct 216 ms 60136 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 20820 KB Output is correct
2 Correct 96 ms 47300 KB Output is correct
3 Correct 108 ms 49504 KB Output is correct
4 Correct 88 ms 49348 KB Output is correct
5 Correct 93 ms 49412 KB Output is correct
6 Correct 67 ms 49432 KB Output is correct
7 Correct 60 ms 42916 KB Output is correct
8 Correct 41 ms 42888 KB Output is correct
9 Correct 26 ms 23192 KB Output is correct
10 Correct 128 ms 49772 KB Output is correct
11 Correct 127 ms 31176 KB Output is correct
12 Correct 259 ms 60956 KB Output is correct
13 Correct 225 ms 58796 KB Output is correct
14 Correct 262 ms 60864 KB Output is correct
15 Correct 226 ms 58800 KB Output is correct
16 Correct 256 ms 60864 KB Output is correct
17 Correct 119 ms 51672 KB Output is correct
18 Correct 216 ms 60136 KB Output is correct
19 Correct 328 ms 60496 KB Output is correct
20 Correct 415 ms 62588 KB Output is correct
21 Correct 329 ms 60524 KB Output is correct
22 Correct 376 ms 58488 KB Output is correct
23 Correct 323 ms 60328 KB Output is correct
24 Correct 408 ms 62640 KB Output is correct
25 Correct 180 ms 54092 KB Output is correct
26 Correct 178 ms 54584 KB Output is correct
27 Correct 280 ms 62124 KB Output is correct