Submission #367227

#	Time	Username	Problem	Language	Result	Execution time	Memory
367227		piddddgy	Fire (JOI20_ho_t5)	C++11	14 / 100	1089 ms	24428 KiB

ho_t5

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define cerr if(false) cerr
#define watch(x) cerr << (#x) << " is " << (x) << endl;
#define endl '\n'
#define ld long double
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(x) (x).begin(), (x).end()

const int maxn = 200500;
int n, q;
int a[maxn];
int seg[4*maxn];

void upd( int pos, int val, int ind, int cl, int cr) {
    if(cl > cr) return;
    if(cl == cr) {
        // cerr << "setting " << ind << " to " << val << endl;
        seg[ind] = val;
    } else {
        int cm = (cl+cr)/2;
 
        if(pos <= cm) {
            upd(pos, val, 2*ind, cl, cm);
        } else {
            upd(pos, val, 2*ind+1, cm+1, cr);
        }
 
        seg[ind] = max(seg[2*ind], seg[2*ind+1]);
    }
}
 
int query(int l, int r, int ind, int cl, int cr) {
    if(cl > cr) return -1e18;
    if(l > r) return -1e18;
    
    if(cl == l and cr == r) {
        return seg[ind];
    }
 
    int cm = (cl+cr)/2;
    return max(query(l, min(cm, r), 2*ind, cl, cm),
            query(max(l, cm+1), r, 2*ind+1, cm+1, cr));
}

int t[maxn], l[maxn], r[maxn];

int psa[maxn];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        upd(i, a[i], 1, 1, n);
    }

    set<int> S;
    for(int i = 1; i <= q; i++) {
        cin >> t[i] >> l[i] >> r[i];
        S.emplace(t[i]);
    }

    if(sz(S) == 1) {
        int k = *S.begin();
        for(int i = 1; i <= n; i++) {
            psa[i] = query(max(1LL, i-k), i, 1, 1, n);
            psa[i] += psa[i-1];
        }

        for(int i = 1; i <= q; i++) {
            cout << psa[r[i]]-psa[l[i]-1] << endl;
        }
    } else {
        for(int i = 1; i <= q; i++) {
            watch(t[i])
            int ans = 0;
            for(int j = l[i]; j <= r[i]; j++) {
                int val = query(max(1LL, j-t[i]), j, 1, 1, n);
                cerr << j << " is " << val << endl;
                cerr << "quried " << max(1LL, j-t[i]) << "," << j << endl;
                ans += val;
            }

            cout << ans << endl;
        }
    }
}

/*



Did you read the bounds?
Did you make typos?
Are there edge cases (N=1?)
Are segay sizes proper?
Integer overflow?
DS reset properly between test cases?
Is using long longs causing TLE?
Are you using floating points?
*/

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