Submission #886494

#	Time	Username	Problem	Language	Result	Execution time	Memory
886494		Caubethieunang	Mountains (NOI20_mountains)	C++17	100 / 100	135 ms	14592 KiB

Mountains

#include <bits/stdc++.h>
#define ll long long
#define LOG 19
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask))
#define ERASE_BIT(mask) (mask)^((mask)&(-mask))
#define left _left
#define right _right
#define task "t"
using namespace std;
const ll INF=1e18;
const int iat=3e5+9;
const int mod=1e9+7;
void fast_IO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
}
int n;
ll h[iat];
struct Fenwick
{
    int bit[iat];
    void update(int pos, int val)
    {
        for(int i=pos; i<=n; i+=i&-i)bit[i]+=val;
    }
    int getSum(int pos)
    {
        int res=0;
        for(int i=pos; i>0; i-=i&-i)res+=bit[i];
        return res;
    }
}left,right;
void compress()
{
    vector <ll> v;
    for(int i=1; i<=n; i++)v.push_back(h[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1; i<=n; i++)h[i]=lower_bound(v.begin(),v.end(),h[i])-v.begin()+1;
}
signed main()
{
    fast_IO();
    cin>>n;
    for(int i=1; i<=n; i++)cin>>h[i];
    compress();
    left.update(h[1],1);
    for(int i=2; i<=n; i++)right.update(h[i],1);
    ll ans=0;
    for(int i=2; i<n; i++)
    {
        right.update(h[i],-1);
        ans+=1LL*left.getSum(h[i]-1)*right.getSum(h[i]-1);
        left.update(h[i],1);
    }
    cout<<ans;
}

Compilation message (stderr)

Mountains.cpp: In function 'void fast_IO()':
Mountains.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Mountains.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 9 / 9
• Subtask 7: 12 / 12