Submission #1146720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146720		koukirocks	Fire (JOI20_ho_t5)	C++20	8 / 100	1096 ms	25596 KiB

ho_t5

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int INF=0x3f3f3f3f;
const ll oo=0x3f3f3f3f3f3f3f3f;
template<class T>
using vvector = vector<vector<T>>;

int main() {
    speed;
    int n,q;
    cin>>n>>q;
    vvector<int> s(n+1,vector<int>(20));
    for (int i=1;i<=n;i++) {
        cin>>s[i][0];
        for (int k=1;k<20;k++) {
            if (i<(1<<k)) continue;
            s[i][k]=max(s[i][k-1],s[i-(1<<k>>1)][k-1]);
        }
    }
    while (q--) {
        int t,l,r;
        cin>>t>>l>>r;
        t++;
        ll ttl=0;
        for (int i=l;i<=r;i++) {
            int nt=t;
            int ni=i;
            nt=min(nt,ni);
            int ans=0;
            for (int k=19;k>=0;k--) {
                if (nt&(1<<k)) {
                    ans=max(ans,s[ni][k]);
                    ni-=(1<<k);
                }
            }
            ttl+=ans;
        }
        cout<<ttl<<"\n";
    }
}

/*
10 1
3 1 4 1 5 9 2 6 5 3
4 2 2
*/

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