Submission #393683

#	Time	Username	Problem	Language	Result	Execution time	Memory
393683		79brue	Fire (JOI20_ho_t5)	C++14	100 / 100	462 ms	50684 KiB

ho_t5

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

struct Query{
    int l, r, idx;
    Query(){}
    Query(int l, int r, int idx): l(l), r(r), idx(idx){}
};

struct maxSegmentTree{
    ll tree[800002];
    void init(int i, int l, int r, ll A[]){
        if(l==r){
            tree[i] = A[l];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    int biggerLim(int i, int l, int r, int x, ll lim, int dir){ /// bigger than lim / dir=0: left, dir=1: right
        if(tree[i] <= lim) return dir==0 ? l-1 : r+1;
        if(l==r) return l;
        int m = (l+r)>>1;
        if(dir == 0){
            if(x<=m) return biggerLim(i*2, l, m, x, lim, dir);
            int tmp = biggerLim(i*2+1, m+1, r, x, lim, dir);
            if(tmp > m) return tmp;
            return biggerLim(i*2, l, m, x, lim, dir);
        }
        else{
            if(m<x) return biggerLim(i*2+1, m+1, r, x, lim, dir);
            int tmp = biggerLim(i*2, l, m, x, lim, dir);
            if(tmp <= m) return tmp;
            return biggerLim(i*2+1, m+1, r, x, lim, dir);
        }
    }
} maxSeg;

struct lazySegmentTree{
    struct Fenwick{
        int n;
        ll tree[400002];
        void addRange(int x, ll y){
            while(x){
                tree[x] += y;
                x -= x&-x;
            }
        }

        ll rangeSum(int x){
            ll ret = 0;
            while(x<=n){
                ret += tree[x];
                x += x&-x;
            }
            return ret;
        }
    } mul, add;
    int n;

    void init(int _n){
        mul.n = add.n = n = _n;
    }

    void addRange(int x, ll y){
        x = min(x, n);
        mul.addRange(x, y);
        add.addRange(n, y*x);
        add.addRange(x, -y*x);
    }

    inline ll rangeSum(int x){
        if(x<=0) return 0;
        return mul.rangeSum(x) * x + add.rangeSum(x);
    }

    inline ll rangeSum(int l, int r){
        return rangeSum(r) - rangeSum(l-1);
    }
} segRight, segDiag;

int n, q;
ll arr[200002];
vector<Query> query[200005];
ll ans[200002];
vector<pair<int, ll> > triangle[200005];

void input();
void makeTriangles();
void sweep();

int main(){
    input();
    makeTriangles();
    sweep();
    for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}

void input(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        scanf("%lld", &arr[i]);
    }
    for(int i=1; i<=q; i++){
        int t, l, r;
        scanf("%d %d %d", &t, &l, &r);
        query[t+1].push_back(Query(l, r, i));
    }
}

void makeTriangles(){
    maxSeg.init(1, 1, n, arr);
    for(int i=1; i<=n; i++){
        triangle[1].push_back(make_pair(i, arr[i]));
        int rLim = maxSeg.biggerLim(1, 1, n, i+1, arr[i]-1, 1);
        if(i<n && rLim <= n && 1<=rLim-i+1 && rLim-i+1<=n+1)
            triangle[rLim-i+1].push_back(make_pair(rLim, -arr[i]));

        int lLim = maxSeg.biggerLim(1, 1, n, i-1, arr[i], 0);
        if(i>1 && lLim >= 1 && 1<=i-lLim+1 && i-lLim+1<=n+1)
            triangle[i-lLim+1].push_back(make_pair(i, -arr[i]));

        if(i<n && i>1 && rLim <= n && lLim >= 1 &&
           1<=(rLim - i + 1) + (i - lLim + 1) - 1 && (rLim - i + 1) + (i - lLim + 1) - 1 <= n+1){
            triangle[(rLim - i + 1) + (i - lLim + 1) - 1].push_back(make_pair(rLim, arr[i]));
        }
    }
}

void sweep(){
    segRight.init(n);
    segDiag.init(2*n+1);

    for(int i=1; i<=n+1; i++){
        for(auto pr: triangle[i]){
            segRight.addRange(pr.first - 1, -pr.second);
            segDiag.addRange((n+1) + pr.first - i, pr.second);
        }

        for(auto qr: query[i]){
            ans[qr.idx] += segRight.rangeSum(qr.l, qr.r);
            ans[qr.idx] += segDiag.rangeSum((n+1) + qr.l - i, (n+1) + qr.r - i);
        }
    }
}

Compilation message (stderr)

ho_t5.cpp: In function 'void input()':
ho_t5.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |         scanf("%lld", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |         scanf("%d %d %d", &t, &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80