oj.uz

Submission #677436

# Submission time Handle Problem Language Result Execution time Memory
677436 2023-01-03T10:57:12 Z qwerasdfzxcl None (JOI15_walls) C++17
100 / 100
 291 ms 38056 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);}
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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7764 KB Output is correct
2 Correct 61 ms 28140 KB Output is correct
3 Correct 67 ms 30112 KB Output is correct
4 Correct 60 ms 30152 KB Output is correct
5 Correct 65 ms 30140 KB Output is correct
6 Correct 49 ms 30224 KB Output is correct
7 Correct 41 ms 23756 KB Output is correct
8 Correct 37 ms 23744 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9556 KB Output is correct
2 Correct 92 ms 28808 KB Output is correct
3 Correct 102 ms 15512 KB Output is correct
4 Correct 210 ms 38012 KB Output is correct
5 Correct 181 ms 35884 KB Output is correct
6 Correct 204 ms 37932 KB Output is correct
7 Correct 197 ms 35868 KB Output is correct
8 Correct 220 ms 38024 KB Output is correct
9 Correct 126 ms 29148 KB Output is correct
10 Correct 167 ms 37472 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7764 KB Output is correct
2 Correct 61 ms 28140 KB Output is correct
3 Correct 67 ms 30112 KB Output is correct
4 Correct 60 ms 30152 KB Output is correct
5 Correct 65 ms 30140 KB Output is correct
6 Correct 49 ms 30224 KB Output is correct
7 Correct 41 ms 23756 KB Output is correct
8 Correct 37 ms 23744 KB Output is correct
9 Correct 19 ms 9556 KB Output is correct
10 Correct 92 ms 28808 KB Output is correct
11 Correct 102 ms 15512 KB Output is correct
12 Correct 210 ms 38012 KB Output is correct
13 Correct 181 ms 35884 KB Output is correct
14 Correct 204 ms 37932 KB Output is correct
15 Correct 197 ms 35868 KB Output is correct
16 Correct 220 ms 38024 KB Output is correct
17 Correct 126 ms 29148 KB Output is correct
18 Correct 167 ms 37472 KB Output is correct
19 Correct 261 ms 35948 KB Output is correct
20 Correct 291 ms 38056 KB Output is correct
21 Correct 273 ms 35988 KB Output is correct
22 Correct 275 ms 34984 KB Output is correct
23 Correct 260 ms 35852 KB Output is correct
24 Correct 287 ms 37932 KB Output is correct
25 Correct 140 ms 29388 KB Output is correct
26 Correct 170 ms 30016 KB Output is correct
27 Correct 235 ms 37568 KB Output is correct