Submission #861136

#	Time	Username	Problem	Language	Result	Execution time	Memory
861136		sleepntsheep	Mountains (NOI20_mountains)	C++17	100 / 100	876 ms	215228 KiB

Mountains

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define N 300005
#define ALL(x) x.begin(), x.end()

#define int long long
int ans, n, a[N];

struct node
{
    node *l, *r;
    int a;
    node(int b) : a(b), l(nullptr), r(nullptr) {}
    node (node *l_, node *r_) : l(l_), r(r_), a((l_?l_->a:0) + (r_?r_->a:0)) {}
};
 
node *build(int l, int r)
{
    if (l == r) return new node(0);
    return new node(build(l, (l+r)/2), build((l+r)/2+1, r));
}
 
node *upd(node *v, int l, int r, int p)
{
    if (l == r) return new node(v->a + 1);
    if (p <= (l+r)/2) return new node(upd(v->l, l, (l+r)/2, p), v->r);
    return new node(v->l, upd(v->r, (l+r)/2+1, r, p));
}
 
int count(node *vl, node *vr, int l, int r, int x, int y)
{
    if (y < l || r < x) return 0;
    if (x <= l && r <= y) return vr->a - vl->a;
    return count(vl->l, vr->l, l, (l+r)/2, x, y) + count(vl->r, vr->r, (l+r)/2+1, r, x, y);
}
 
node *root[N];
vector<int> C;

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], C.push_back(a[i]);
    sort(ALL(C));
    root[0] = build(1, n);
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(ALL(C), a[i]) - C.begin() + 1,
         root[i] = upd(root[i-1], 1, n, a[i]);

    for (int i = 1; i <= n; ++i) 
    {
        int lft = count(root[0], root[i], 1, n, 0, a[i] - 1);
        int rgt = count(root[i], root[n], 1, n, 0, a[i] - 1);
        ans += lft * rgt;
        //cout << "E " << lft << ' ' << rgt<<endl;
    }
    cout << ans;

    return 0;
}

Compilation message (stderr)

Mountains.cpp: In constructor 'node::node(long long int)':
Mountains.cpp:24:9: warning: 'node::a' will be initialized after [-Wreorder]
   24 |     int a;
      |         ^
Mountains.cpp:23:11: warning:   'node* node::l' [-Wreorder]
   23 |     node *l, *r;
      |           ^
Mountains.cpp:25:5: warning:   when initialized here [-Wreorder]
   25 |     node(int b) : a(b), l(nullptr), r(nullptr) {}
      |     ^~~~

• 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