oj.uz

Submission #1086768

# Submission time Handle Problem Language Result Execution time Memory
1086768 2024-09-11T12:37:38 Z Muhammad_Aneeq Pilot (NOI19_pilot) C++17
23 / 100
 163 ms 13904 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int const N=1e6+10,LG=22;
int fen[N]={};
int sp[N][LG];
int h[N];
int n,q;
void build()
{
    for (int i=0;i<n;i++)
        sp[i][0]=h[i];
    for (int i=1;(1<<i)<=n;i++)
        for (int j=0;j+(1<<i)-1<n;j++)
            sp[j][i]=max(sp[j][i-1],sp[j+(1<<(i-1))][i-1]);
}
int get(int l,int r)
{
    int lg=log2(r-l+1);
    return max(sp[l][lg],sp[r-(1<<lg)+1][lg]);
}
inline void solve()
{
    cin>>n>>q;
    for (int i=0;i<n;i++)
        cin>>h[i];
    build();
    vector<pair<int,int>>d;
    for (int i=0;i<n;i++)
        d.push_back({h[i],i});
    sort(begin(d),end(d));
    long long ANS[q]={};
    vector<pair<int,int>>Q;
    for (int i=0;i<q;i++)
    {
        int x;
        cin>>x;
        Q.push_back({x,i});
    }
    sort(begin(Q),end(Q));
    int i=0;
    long long pre=0;
    for (auto k:Q)
    {
        int mx=k.first;
        long long ans=pre;
        while (i<n&&d[i].first<=mx)
        {
            int j=d[i].second;
            int st=-1,en=j;
            while (st+1<en)
            {
                int mid=(st+en)/2;
                if (get(mid,j)==d[i].first)
                    en=mid;
                else
                    st=mid;
            }
            long long l1=j-en+1;
            st=j,en=n;
            while (st+1<en)
            {
                int mid=(st+en)/2;
                if (get(j,mid)==d[i].first)
                    st=mid;
                else
                    en=mid;
            }
            long long l2=st-j+1;
            ans+=(l1-1)*(l2-1);
            ans+=l2+l1-2;
            ans++;
            i++;
        }
        ANS[k.second]=ans;
        pre=ans;
    }  
    for (auto i:ANS)
        cout<<i<<'\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 13076 KB Output is correct
2 Correct 115 ms 13128 KB Output is correct
3 Correct 110 ms 13140 KB Output is correct
4 Correct 114 ms 13640 KB Output is correct
5 Correct 114 ms 12844 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 13368 KB Output is correct
2 Correct 112 ms 13132 KB Output is correct
3 Correct 110 ms 13132 KB Output is correct
4 Correct 117 ms 13904 KB Output is correct
5 Correct 115 ms 13648 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -