Submission #1248141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248141		orzngaiha	Pilot (NOI19_pilot)	C++20	100 / 100	833 ms	95976 KiB

pilot

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
int n,q,ans[N];
pair<int,int> a[N],b[N];
struct Node{
  int L,R,s;

} st[4*N];
void update(int id,int l,int r,int i,int v)
{
    if(i < l or i > r)
        return;
    if(l == r)
    {
        st[id].L = 1;
        st[id].R = 1;
        st[id].s = 1;
        return;
    }
    int mid = (l+r)/2;
    update(2*id,l,mid,i,v);
    update(2*id+1,mid+1,r,i,v);
    st[id].s = st[2*id].s + st[2*id+1].s;
    if(st[2*id].R > 0 and st[2*id+1].L > 0)
    {
        int v = st[2*id].R  + st[2*id+1].L ;
        int x = st[2*id].R ,y = st[2*id+1].L;
        st[id].s = st[id].s + v*(v+1)/2 - x*(x+1)/2 - y*(y+1)/2;
    }

    if(st[2*id].L == (mid-l+1))
      st[id].L = st[2*id].L + st[2*id+1].L;
    else
           st[id].L = st[2*id].L;
      if(st[2*id+1].R == (r-mid))
        st[id].R = st[2*id+1].R + st[2*id].R;
    else
        st[id].R = st[2*id+1].R;
}
signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for(int i = 1;i <= n;i++)
    {
        cin>>a[i].first;
        a[i].second = i;
    }
    for(int i = 1;i <= q;i++)
    {
        cin>>b[i].first;
        b[i].second = i;
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+q);
    int l = 1;
    for(int i = 1;i <= q;i++)
    {
        while(a[l].first <= b[i].first)
        {
            update(1,1,n,a[l].second,1);
            l++;
        }
       ans[b[i].second] = st[1].s;
    }
    for(int i = 1;i <= q;i++)
        cout<<ans[i]<<'\n';
}

• 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: 11 / 11