Submission #762824

#	Time	Username	Problem	Language	Result	Execution time	Memory
762824		HoriaHaivas	Pilot (NOI19_pilot)	C++14	55 / 100	1064 ms	15424 KiB

pilot

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

int rmq[20][1000001];
int v[1000001];

int query (int l, int r)
{
    int logi;
    logi=log2(r-l+1);
    return max(rmq[logi][l],rmq[logi][r-(1<<logi)+1]);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q,i,j,r,pas,ans,value;
    cin >> n >> q;
    for (i=1;i<=n;i++)
    {
         cin >> v[i];
         rmq[0][i]=v[i];
    }
    for (i=1;i<=19;i++)
    {
         for (j=1;j+(1<<i)-1<=n;j++)
         {
              rmq[i][j]=max(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
         }
    }
    for (i=1;i<=q;i++)
    {
         cin >> value;
         ans=0;
         for (j=1;j<=n;j++)
         {
             if (value>=v[j])
             {
                r=j;
                pas=(1<<19);
                while (pas)
                {
                    if (r+pas<=n && query(j,r+pas)<=value)
                        r+=pas;
                    pas=pas/2;
                }
                if (i==1)
                {
                    debugs(j);
                    debug(r);
                }
                ans+=r-j+1;
             }
         }
         cout << ans << "\n";
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 0 / 9
• Subtask 7: 0 / 14
• Subtask 8: 10 / 10
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11