oj.uz

Submission #393673

# Submission time Handle Problem Language Result Execution time Memory
393673 2021-04-24T08:26:08 Z 79brue Fire (JOI20_ho_t5) C++14
7 / 100
 1000 ms 62320 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 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<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++){
        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[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(){
    sort(query+1, query+q+1);

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

        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 sweep()':
ho_t5.cpp:138:9: warning: unused variable 'pnt' [-Wunused-variable]
  138 |     int pnt = 0, qpnt = 1;
      |         ^~~
ho_t5.cpp: In function 'void input()':
ho_t5.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |         scanf("%lld", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |         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 3 ms 4940 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5108 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 4 ms 5068 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 4 ms 5068 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 4 ms 5068 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 4 ms 5088 KB Output is correct
21 Correct 4 ms 5068 KB Output is correct
22 Correct 4 ms 5068 KB Output is correct
23 Correct 4 ms 5068 KB Output is correct
24 Correct 4 ms 5068 KB Output is correct
25 Correct 4 ms 5068 KB Output is correct
26 Correct 4 ms 5068 KB Output is correct
27 Correct 4 ms 5068 KB Output is correct
28 Correct 4 ms 5068 KB Output is correct
29 Correct 4 ms 5068 KB Output is correct
30 Correct 4 ms 5068 KB Output is correct
31 Correct 4 ms 5068 KB Output is correct
32 Correct 4 ms 5068 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 992 ms 55200 KB Output is correct
3 Correct 963 ms 60428 KB Output is correct
4 Execution timed out 1027 ms 62320 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 50680 KB Output is correct
2 Correct 962 ms 56368 KB Output is correct
3 Correct 976 ms 56840 KB Output is correct
4 Correct 990 ms 55128 KB Output is correct
5 Correct 958 ms 56720 KB Output is correct
6 Correct 957 ms 55532 KB Output is correct
7 Correct 937 ms 55408 KB Output is correct
8 Correct 947 ms 56456 KB Output is correct
9 Correct 949 ms 55264 KB Output is correct
10 Correct 936 ms 55124 KB Output is correct
11 Correct 942 ms 55476 KB Output is correct
12 Correct 936 ms 56652 KB Output is correct
13 Correct 933 ms 55416 KB Output is correct
14 Correct 933 ms 56612 KB Output is correct

Subtask #5
0 / 80.0

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