oj.uz

Submission #647386

# Submission time Handle Problem Language Result Execution time Memory
647386 2022-10-02T10:56:09 Z ck_platypus Fire (JOI20_ho_t5) C++14
0 / 100
 161 ms 20056 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 150 ms 20056 KB Output is correct
3 Incorrect 147 ms 20048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 161 ms 15972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 12472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -