oj.uz

Submission #861134

# Submission time Handle Problem Language Result Execution time Memory
861134 2023-10-15T12:08:36 Z sleepntsheep Mountains (NOI20_mountains) C++17
2 / 100
 378 ms 214636 KB 
#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 = 0; i < n; ++i) cin >> a[i], C.push_back(a[i]);
    sort(ALL(C));
    root[0] = build(0, n);
    for (int i = 0; i < n; ++i) a[i] = lower_bound(ALL(C), a[i]) - C.begin(),
         root[i+1] = upd(root[i], 0, n, a[i]);

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

    return 0;
}

Compilation message

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 355 ms 212784 KB Output is correct
3 Correct 378 ms 212928 KB Output is correct
4 Correct 341 ms 212560 KB Output is correct
5 Correct 345 ms 213692 KB Output is correct
6 Correct 359 ms 213456 KB Output is correct
7 Correct 354 ms 212488 KB Output is correct
8 Correct 350 ms 213200 KB Output is correct
9 Correct 328 ms 212624 KB Output is correct
10 Correct 340 ms 212672 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 264 ms 214636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 264 ms 214636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 264 ms 214636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 355 ms 212784 KB Output is correct
3 Correct 378 ms 212928 KB Output is correct
4 Correct 341 ms 212560 KB Output is correct
5 Correct 345 ms 213692 KB Output is correct
6 Correct 359 ms 213456 KB Output is correct
7 Correct 354 ms 212488 KB Output is correct
8 Correct 350 ms 213200 KB Output is correct
9 Correct 328 ms 212624 KB Output is correct
10 Correct 340 ms 212672 KB Output is correct
11 Incorrect 264 ms 214636 KB Output isn't correct
12 Halted 0 ms 0 KB -