oj.uz

답안 #677435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
677435 2023-01-03T10:50:07 Z qwerasdfzxcl 방벽 (JOI15_walls) C++17
100 / 100
 412 ms 56984 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, 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

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 20692 KB Output is correct
2 Correct 91 ms 46828 KB Output is correct
3 Correct 102 ms 48976 KB Output is correct
4 Correct 87 ms 48952 KB Output is correct
5 Correct 97 ms 49076 KB Output is correct
6 Correct 63 ms 48980 KB Output is correct
7 Correct 39 ms 42948 KB Output is correct
8 Correct 39 ms 42932 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 22796 KB Output is correct
2 Correct 124 ms 47840 KB Output is correct
3 Correct 116 ms 28940 KB Output is correct
4 Correct 283 ms 56956 KB Output is correct
5 Correct 224 ms 54968 KB Output is correct
6 Correct 260 ms 56984 KB Output is correct
7 Correct 243 ms 54816 KB Output is correct
8 Correct 287 ms 56892 KB Output is correct
9 Correct 117 ms 48068 KB Output is correct
10 Correct 255 ms 56516 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 20692 KB Output is correct
2 Correct 91 ms 46828 KB Output is correct
3 Correct 102 ms 48976 KB Output is correct
4 Correct 87 ms 48952 KB Output is correct
5 Correct 97 ms 49076 KB Output is correct
6 Correct 63 ms 48980 KB Output is correct
7 Correct 39 ms 42948 KB Output is correct
8 Correct 39 ms 42932 KB Output is correct
9 Correct 23 ms 22796 KB Output is correct
10 Correct 124 ms 47840 KB Output is correct
11 Correct 116 ms 28940 KB Output is correct
12 Correct 283 ms 56956 KB Output is correct
13 Correct 224 ms 54968 KB Output is correct
14 Correct 260 ms 56984 KB Output is correct
15 Correct 243 ms 54816 KB Output is correct
16 Correct 287 ms 56892 KB Output is correct
17 Correct 117 ms 48068 KB Output is correct
18 Correct 255 ms 56516 KB Output is correct
19 Correct 325 ms 54932 KB Output is correct
20 Correct 412 ms 56984 KB Output is correct
21 Correct 322 ms 54916 KB Output is correct
22 Correct 351 ms 53292 KB Output is correct
23 Correct 356 ms 54920 KB Output is correct
24 Correct 401 ms 56892 KB Output is correct
25 Correct 149 ms 48344 KB Output is correct
26 Correct 174 ms 49032 KB Output is correct
27 Correct 277 ms 56540 KB Output is correct