Submission #1178644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178644		amine_aroua	Fire (JOI20_ho_t5)	C++20	7 / 100	348 ms	64004 KiB

ho_t5

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int LG = 19 , MAXN = 4e5;
int dp[LG + 1][MAXN + 1];
vector<int> lg(MAXN + 1);
void precompute(vector<int> &v)
{   
    for(int i = 0 ;i < (int)v.size() ; i++)
    {
        dp[0][i] = v[i];
    }
    for(int i = 1 ; i < LG ; i++)
    {
        for(int j = 0 ; j + (1<<i) <= MAXN ; j++)
        {
            dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j + (1<<(i - 1))]);
        }
    }
}
int max_query(int l , int r)
{
    int f = lg[r - l + 1];
    return max(dp[f][l] , dp[f][r - (1<<f) + 1]);
}
signed main()
{
    int n , q;
    cin>>n>>q;
    vector<int> s(2 * n + 1);
    for(int i = n ;i < 2 * n ; i++)
    {
        cin>>s[i];
    }
    lg[1] = 0;
    for(int i = 2 ; i <= MAXN ; i++)
    {
        lg[i] = lg[i >> 1] + 1;
    }
    precompute(s);
    for(int i = 0 ; i < q ; i++)
    {
        int t , l , r;
        cin>>t>>l>>r;
        l+=n-1;
        cout<<max_query(l - t , l)<<'\n';
    }
}

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