Submission #1086869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086869		SyedSohaib_123	Pilot (NOI19_pilot)	C++17	89 / 100	1048 ms	137060 KiB

pilot

#include<bits/stdc++.h>



using namespace std;



#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")



#define str string
#define append push_back
#define int long long
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define endl "\n"
#define all(ls) ls.begin(),ls.end()
#define sorted(ls) sort(ls.begin(),ls.end());
#define reversed(ls) reverse(ls.begin(),ls.end());
#define print(n) for(auto i:n)cout<<i<<' ';cout<<endl;
#define input(n,ls,m) vector<n>ls(m);for(int i=0;i<m;i++)cin>>ls[i];
#define ff first
#define ss second



int const N=3e5+10;
int const LG=21;



int mod=1e9+7;
int mod1=998244353;



int sum_(vector<int>ls){int s=0;for(auto i:ls)s+=i;return s;}
int min(int a,int b){if (a>b){return b;}return a;}
int max(int a,int b){if (a<b){return b;}return a;}



//......................................tHe ReaL cOdE beGinS HerE......................................//



void solve(){
    int n,Q;
    cin>>n>>Q;
    int ls[n+1];
    ls[0]=0;
    for(int i=1;i<=n;i++){
        cin>>ls[i];
    }
    vector<int> q;
    vector<pair<int,int>>m;
    for(int i=0;i<Q;i++){
        int a;
        cin>>a;
        q.append(a);
        m.append({a,i});
    }
    sorted(m);
    sorted(q);
    set<pair<int,int>>s;
    set<int>t;
    s.clear();
    int ans=0;
    int last=0;
    for(int i=1;i<=n;i++){
        if(ls[i]>q[0]) s.insert({ls[i],i});
        else {ans+=i-last;continue;}
        last=i;
        t.insert(i);
    }
    // print(t);
    m[0].ff=ans;
    swap(m[0].ff,m[0].ss);
    for(int i=1;i<Q;i++){
        int a=q[i];
        int cnt=0;
        while(s.size() and (*s.begin()).ff<=a){
            int x=(*s.begin()).ff,ind=(*s.begin()).ss;
            cnt++;
            int l,r;
            if(ind==*t.begin()) l=1;
            else l=(*(--t.find(ind)))+1;
            if(ind==*t.rbegin()) r=n;
            else r=(*(++t.find(ind)))-1;
            ans+=1+(ind-l)*(r-ind)+(r-ind)+(ind-l);
            t.erase(t.find(ind));
            s.erase(s.begin());
        }
        m[i].ff=ans;
        swap(m[i].ff,m[i].ss);
    }
    sorted(m);
    for(auto [i,j]:m) cout<<j<<endl;
} 



signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
        solve();
}

Compilation message (stderr)

pilot.cpp: In function 'void solve()':
pilot.cpp:87:17: warning: unused variable 'x' [-Wunused-variable]
   87 |             int x=(*s.begin()).ff,ind=(*s.begin()).ss;
      |                 ^

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