Submission #647386

#	Time	Username	Problem	Language	Result	Execution time	Memory
647386		ck_platypus	Fire (JOI20_ho_t5)	C++14	0 / 100	161 ms	20056 KiB

ho_t5

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <bitset>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <cstring>
#include <fstream>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pll pair<ll, ll>
#define plpll pair<ll, pll>
#define pii pair<int, int>
#define f first
#define s second
#define inf 1000000000000000000
#define endl '\n'
int seg[800010] = {0};
void modify(int cur, int l, int r, int ind, int val){
    if (r <= l) return;
    if (r - l == 1 && l == ind){
        seg[cur] = val;
        return;
    }
    int mid = (l + r) / 2;
    if (ind < mid) modify(cur * 2, l, mid, ind, val);
    else modify(cur * 2 + 1, mid, r, ind, val);
    seg[cur] = max(seg[cur * 2], seg[cur * 2 + 1]);
}
int query(int cur, int l, int r, int ql, int qr){
    if (r <= l || ql >= r || qr <= l) return 0;
    if (ql <= l && qr >= r) return seg[cur];
    int mid = (l + r) / 2;
    return max(query(cur * 2, l, mid, ql, qr), query(cur * 2 + 1, mid, r, ql, qr));
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n, q;
    cin >> n >> q;
    ll s[n], t[n], l[n], r[n], mxt=0, mnt=n, mxlr=0;
    for(int i=0;i<n;i++) cin >> s[i], modify(1, 0, n, i, s[i]);
    for(int i=0;i<q;i++) cin >> t[i] >> l[i] >> r[i], mxt=max(mxt, t[i]), mnt=min(mnt, t[i]), mxlr=max(mxlr, r[i]-l[i]);
    if(mxlr==0){
        for(int i=0;i<q;i++){
            cout << query(1, 0, n, max(0ll, l[i]-t[i]-1), l[i]) << endl;
        }
    }else if(mxt==mnt){
        ll cool[n];
        for(int i=0;i<n;i++) cool[i]=query(1, 0, n, max(0ll, i-t[0]), i+1);
        ll pre[n+1];
        pre[0]=0;
        for(int i=1;i<=n;i++) pre[i]=pre[i-1]+cool[i-1];
        for(int i=0;i<q;i++) cout << pre[r[i]]-pre[l[i]-1] << endl;
    }
    return 0;
}

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