Submission #494781

#	Time	Username	Problem	Language	Result	Execution time	Memory
494781		ryangohca	Fire (JOI20_ho_t5)	C++17	100 / 100	495 ms	58584 KiB

ho_t5

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ti3 tuple<int, int, int>
#define ti4 tuple<int, int, int, int>
#define int long long
// We are dancing on fire ~~  ~ Seunghee, Dun Dun Dance
using namespace std;
// Notice that in a 2d array (pos, t), each number will form a parallelogram in the array.
// for eg, sample input (look at 6):
// 93265
// 99366
// 99966
// 99996
// 99999
// for each parallelogram, we can decompose it into 3 triangles starting from t=0.
// for eg, 6 in sample input:
// .XX6Y
// ..X66
// ...66
// ....6
// .....
// left point of triangle is 1 + (largest leftmost idx >= a[i]), right point of triangle is
// (smallest rightmost idx > a[i]) - 1;
// updating a triangle = updating a parallelogram [l, inf) starting from t=0 and 
// updating a rectangle [r+1, inf) starting from t=0
// so actual update on triangle will be the difference b/w the 2 intersections.
// ie. actual_range_sum0(l, r) = range_sum_par0(l, r) - range_sum_rect0(l, r);
// note: if rightmost / leftmost elem does not exist just use a very big/small number
// Moreover, all (actual) updates are parallelograms, so
// B..XX
// XC..X
// abc
// notice that b to c = a to b (B and C are equal unless the parallelogram of B ends there)
// so range_sum(l, r, t) = range_sum_par(l, r, t) - range_sum_rect(l, r, t)
//                       = range_sum_par0(l - h + 1, r - h + 1, t) - range_sum_rect0(l, r)
// when h is the height of the parallelogram, which is basically t + 1(0-indexed)
// to ensure that B and C are equal (I think? - but we should remove those out of range triangles anyways)
// we sweep line by T, and remove triangles that are out of range (height < t);
int arr[200005], L[200005], R[200005], ans[200005];
vector<ti3> heights[200005];
vector<ti3> queries[200005];
struct fenwick{
    int N;
    int fw[400010], fw2[400010];
    int off = 200002;
    fenwick(int N): N(N){
        memset(fw, 0, sizeof fw);
        memset(fw2, 0, sizeof fw2);
    }
    void update(int x, int y, int v) { //inclusive
        x += off; y += off;
        for (int tx=x; tx <= N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
        for (int ty=y+1; ty <= N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
    }
    int sum (int x) {
        int res = 0;
        for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
        return res;    
    }
    int range_sum(int x, int y) { //inclusive
        x += off; y += off;
        return sum(y)-sum(x-1);
    }
} *parfw = new fenwick(400005), *rectfw = new fenwick(400005);
int n;
void tri(int l, int r, int v, bool upd){
    if (l > r) return;
    parfw->update(l, n+1, v);
    rectfw->update(r+1, n+1, v);
    if (upd){
        int height = r-l+1;
        if (height <= n) heights[height].push_back({l, r, -v}); 
    }
}
main(){
    int q; cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    stack<int> nums;
    for (int i = 1; i <= n; i++){
        while (!nums.empty() && arr[nums.top()] < arr[i]) nums.pop();
        L[i] = (nums.empty()?-n-1:nums.top());
        nums.push(i);
    }
    while (!nums.empty()) nums.pop();
    for (int i = n; i > 0; i--){
        while (!nums.empty() && arr[nums.top()] <= arr[i]) nums.pop();
        R[i] = (nums.empty()?n+1:nums.top());
        nums.push(i);
    }
    for (int i = 1; i <= n; i++){
        tri(L[i]+1, R[i]-1, arr[i], true); // large triangle
        tri(L[i]+1, i-1, -arr[i], true); // small triangle
        tri(i+1, R[i]-1, -arr[i], true); // small triangle
    }
    for (int i = 1; i <= q; i++){
        int t, l, r; cin >> t >> l >> r;
        queries[t].push_back({l, r, i});
    }
    // time starts from 0, so triangles with heights t or below should be removed
    for (int t = 1; t <= n; t++){
        for (auto [l, r, v]: heights[t]) tri(l, r, v, false);
        for (auto [l, r, i]: queries[t]) ans[i] = parfw->range_sum(l-t, r-t) - rectfw->range_sum(l, r);
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

ho_t5.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main(){
      | ^~~~

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