Submission #1082848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082848		MrPavlito	Mountains (NOI20_mountains)	C++17	100 / 100	367 ms	41668 KiB

Mountains

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 3e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;

vector<int> niz(MAXN);
vector<int> preseg(MAXN<<2);
vector<int> sufseg(MAXN<<2);


void update(int nod, int tl, int tr,int index, int v, vector<int>&seg)
{
    if(tl == tr)
    {
        seg[nod] += v;
        return;
    }
    int mid = tl+tr>>1;
    if(index<=mid)update(nod<<1, tl, mid, index, v, seg);
    else update(nod<<1|1, mid+1, tr, index, v, seg);
    seg[nod] = seg[nod<<1] + seg[nod<<1|1];
}


int query(int nod, int tl, int tr, int l, int r, vector<int>&seg)
{
    if(tl>tr || tl>r || tr<l)return 0;
    if(tl>=l && tr<=r)return seg[nod];
    int mid = tl+tr>>1;
    return query(nod<<1, tl, mid, l, r, seg) + query(nod<<1|1, mid+1,  tr, l, r, seg);
}


signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        int n;
        cin >> n;
        vector<int> compress;
        unordered_map<int,int> vals;
        for(int i=1; i<=n; i++)
        {
            cin >> niz[i];
            compress.pb(niz[i]);
        }
        sort(all(compress));
        //compress.erase(unique(all(compress), compress.end()));
        int c = 0;
        for(int i=0; i<(int)compress.size(); i++)if(!vals.count(compress[i]))vals[compress[i]] = ++c;
        for(int i=1; i<=n; i++)niz[i] = vals[niz[i]];
        for(int i=3; i<=n; i++)update(1,1,n,niz[i], 1, sufseg);
        update(1,1,n, niz[1], 1,preseg);
        long long rez = 0;

        for(int i=2; i<n; i++)
        {
            int q1 = query(1,1,n,1,niz[i]-1, preseg);
            int q2 = query(1,1,n,1,niz[i]-1, sufseg);
            rez+=q1*q2;
            update(1,1,n, niz[i],1, preseg);
            update(1,1,n, niz[i+1],-1, sufseg);
        }

        cout << rez << endl;




    }
}

/*
6
500 20 900 0 900 70
 */

Compilation message (stderr)

Mountains.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, std::vector<long long int>&)':
Mountains.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = tl+tr>>1;
      |               ~~^~~
Mountains.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int, std::vector<long long int>&)':
Mountains.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = tl+tr>>1;
      |               ~~^~~

• 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