Submission #1192172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192172		quocbaoo	Pilot (NOI19_pilot)	C++20	100 / 100	807 ms	95912 KiB

pilot

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
ll kq[1000004];pair<ll,ll> a[1000004],b[1000004];
struct Node{
    ll d,c,to;
};Node st[4000005];
ll pt(ll z){
    return z*(z+1)/2;
}
void update(int id,int l,int r,int u,int v){
    if (l>u||r<u) return ;
    if (l==r){
        st[id].d=1;st[id].c=1;st[id].to=1;
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,u,v);update(id*2+1,mid+1,r,u,v);
    st[id].to=st[id*2].to+st[id*2+1].to;
    if (st[id*2].c>0&&st[id*2+1].d>0) {
        st[id].to+=(pt(st[id*2].c+st[id*2+1].d)-pt(st[id*2].c)-pt(st[id*2+1].d));
    }
    if (st[id*2].d==mid-l+1) st[id].d=st[id*2].d+st[id*2+1].d;else st[id].d=st[id*2].d;
    if (st[id*2+1].c==r-mid) st[id].c=st[id*2+1].c+st[id*2].c;else st[id].c=st[id*2+1].c;
}
int main() {
    if (fopen("THAYDOISO.inp","r")){
        freopen("THAYDOISO.inp","r",stdin);
        freopen("THAYDOISO.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q;cin>>n>>q;
    for (int i=1;i<=n;i++) {
        cin>>a[i].fi;a[i].se=i;
    }
    for (int i=1;i<=q;i++){
        cin>>b[i].fi;b[i].se=i;
    }
    sort(a+1,a+n+1);
    sort(b+1,b+q+1);
    ll ans=0;
    b[0].fi=-1;a[n+1].fi=1e9;int d=1;
    for (int i=1;i<=q;i++){
        if (b[i].fi==b[i-1].fi){
            kq[b[i].se]=ans;continue;
        }
        while (b[i].fi>=a[d].fi){
            update(1,1,n,a[d].se,1);d++;
        }
        ans=st[1].to;
        kq[b[i].se]=ans;
    }
    for (int i=1;i<=q;i++) cout<<kq[i]<<'\n';
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen("THAYDOISO.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pilot.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen("THAYDOISO.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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