oj.uz

Submission #680220

# Submission time Handle Problem Language Result Execution time Memory
680220 2023-01-10T09:34:23 Z raysh07 Mountains (NOI20_mountains) C++17
64 / 100
 298 ms 51592 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int n;
const int maxn = 3e5 + 69;
int a[maxn];
set <int> send;
map <int, int> comp;
int seg[4*maxn];
int b[maxn];

void Update(int l, int r, int pos, int qpos, int qval){
    seg[pos]+=qval;
    if (l==r) return;
    int mid = (l+r)/2;
    if (qpos<=mid) Update(l, mid, pos*2, qpos, qval);
    else Update(mid + 1, r, pos*2 + 1, qpos, qval);
}

int Query(int l, int r, int pos, int ql, int qr){
    if (l>=ql && r<=qr) return seg[pos];
    else if (l>qr || r<ql) return 0;
    
    int mid = (l+r)/2;
    return Query(l, mid, pos*2, ql, qr) + Query(mid + 1, r, pos*2 + 1, ql, qr);
}

void compress()
{
    int p = 1;
    for (auto x: send){
        comp[x] = p++;
    }
}

void Solve() 
{
    cin>>n;
    for (int i=1; i<=n; i++){
        cin>>a[i];
        send.insert(a[i]);
    }
    compress();
    
    for (int i=1; i<=n; i++)
    a[i] = comp[a[i]];
    
    for (int i=1; i<=n; i++){
        b[i] = Query(1, n, 1, 1, a[i]-1);
        Update(1, n, 1, a[i], 1);
    }
    
    for (int i=0; i<maxn; i++)
    seg[i] = 0;
    
    int sum = 0;
    
    for (int i=n; i>=1; i--){
        b[i] *= Query(1, n, 1, 1, a[i]-1);
        Update(1, n, 1, a[i], 1);
        
        sum += b[i];
    }
    
    cout<<sum;
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 298 ms 51592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 9.0

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

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2656 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2656 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 12 ms 4052 KB Output is correct
12 Correct 12 ms 4052 KB Output is correct
13 Correct 12 ms 4052 KB Output is correct
14 Correct 12 ms 4052 KB Output is correct
15 Correct 13 ms 4132 KB Output is correct
16 Correct 13 ms 4052 KB Output is correct
17 Correct 12 ms 4052 KB Output is correct
18 Correct 10 ms 3416 KB Output is correct
19 Correct 6 ms 2900 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct

Subtask #6
0 / 9.0

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

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 298 ms 51592 KB Output isn't correct
3 Halted 0 ms 0 KB -