oj.uz

Submission #393671

# Submission time Handle Problem Language Result Execution time Memory
393671 2021-04-24T08:22:58 Z 79brue Fire (JOI20_ho_t5) C++14
1 / 100
 1000 ms 47344 KB 
#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 Triangle{
    int x, y; ll w;
    Triangle(){}
    Triangle(int x, int y, ll w): x(x), y(y), w(w){}
    bool operator<(const Triangle &r)const{
        return x<r.x;
    }
};

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

    bool operator<(const Query &r)const{
        return t < r.t;
    }
};

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{
    ll tree[1600002], lazy[1600002];

    void propagate(int i, int l, int r){
        tree[i] += lazy[i] * (r-l+1);
        if(l!=r){
            lazy[i*2] += lazy[i];
            lazy[i*2+1] += lazy[i];
        }
        lazy[i] = 0;
    }

    void addRange(int i, int l, int r, int s, int e, ll val){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] += val;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        addRange(i*2, l, m, s, e, val);
        addRange(i*2+1, m+1, r, s, e, val);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    ll rangeSum(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return rangeSum(i*2, l, m, s, e) + rangeSum(i*2+1, m+1, r, s, e);
    }
} segRight, segDiag;

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

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++){
        scanf("%d %d %d", &query[i].t, &query[i].l, &query[i].r);
        query[i].idx = i;
        query[i].t++;
    }
}

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

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

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

void sweep(){
    sort(query+1, query+q+1);

    int pnt = 0, qpnt = 1;
    for(int i=1; i<=n+1; i++){
        while(pnt < (int)triangle.size() && triangle[pnt].x <= i){
            Triangle tri = triangle[pnt++];
            segRight.addRange(1, 1, n, 1, tri.y - 1, -tri.w);
            segDiag.addRange(1, -n, n, -n, tri.y - tri.x, tri.w);
        }

        while(qpnt <= q && query[qpnt].t <= i){
            Query qr = query[qpnt++];
            ans[qr.idx] += segRight.rangeSum(1, 1, n, qr.l, qr.r);
            ans[qr.idx] += segDiag.rangeSum(1, -n, n, qr.l - qr.t, qr.r - qr.t);
        }
    }
}

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 408 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Execution timed out 1086 ms 44136 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Execution timed out 1093 ms 47344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 45456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 408 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Execution timed out 1086 ms 44136 KB Time limit exceeded
34 Halted 0 ms 0 KB -