oj.uz

Submission #439070

# Submission time Handle Problem Language Result Execution time Memory
439070 2021-06-29T07:28:38 Z meatrow Mountains (NOI20_mountains) C++17
24 / 100
 624 ms 14344 KB 
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int t[1200000];
int g[300000];
int left1[300000], right1[300000];
void update (int v, int tl, int tr, int h) {
    if (tl == tr)
        t[v]++;
    else {
        int tm = (tl + tr) / 2;
        if (h <= tm)
            update (v*2, tl, tm, h);
        else
            update (v*2+1, tm+1, tr, h);
        t[v] = t[v*2] + t[v*2+1];
    }
}
int sum (int v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return sum (v*2, tl, tm, l, min(r,tm))
           + sum (v*2+1, tm+1, tr, max(l,tm+1), r);
}
int main(){
    int n;
    cin >> n;
    vector<int>b;
    for(int i = 0; i < n; i++){
        cin >> g[i];
        b.push_back(g[i]);
    }
    sort(b.begin(), b.end());
    map<int,int>c;
    for(int i = 0; i < b.size(); i++){
        c[b[i]] = i;
    }
    for(int i = 0; i < n; i++){
        g[i] = c[g[i]];
    }
    update(1, 0, n, g[0]);
    for(int i = 1; i < n - 1; i++){
        left1[i] = sum(1, 0, n, 0, g[i] - 1);
        update(1, 0, n, g[i]);
    }
    memset(t, 0, sizeof(t[0]) * 1200000);
    update(1, 0, n, g[n - 1]);
    for(int i = n - 2; i >= 1; i--){
        right1[i] = sum(1, 0, n, 0, g[i] - 1);
        update(1, 0, n, g[i]);
    }
    long long int ans = 0;
    for(int i = 1; i < n - 1; i++){
        ans += 1LL * left1[i] * right1[i];
    }
    cout << ans;
    return 0;
}

Compilation message

Mountains.cpp: In function 'int main()':
Mountains.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i < b.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 150 ms 9760 KB Output is correct
3 Correct 164 ms 9688 KB Output is correct
4 Correct 148 ms 9680 KB Output is correct
5 Correct 149 ms 9672 KB Output is correct
6 Correct 148 ms 9692 KB Output is correct
7 Correct 167 ms 9764 KB Output is correct
8 Correct 157 ms 9760 KB Output is correct
9 Correct 149 ms 9700 KB Output is correct
10 Correct 153 ms 9768 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 9776 KB Output is correct
2 Correct 209 ms 9796 KB Output is correct
3 Correct 228 ms 9764 KB Output is correct
4 Correct 212 ms 9676 KB Output is correct
5 Correct 207 ms 9776 KB Output is correct
6 Correct 205 ms 9780 KB Output is correct
7 Correct 205 ms 9772 KB Output is correct
8 Correct 211 ms 9784 KB Output is correct
9 Correct 196 ms 9776 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 9776 KB Output is correct
2 Correct 209 ms 9796 KB Output is correct
3 Correct 228 ms 9764 KB Output is correct
4 Correct 212 ms 9676 KB Output is correct
5 Correct 207 ms 9776 KB Output is correct
6 Correct 205 ms 9780 KB Output is correct
7 Correct 205 ms 9772 KB Output is correct
8 Correct 211 ms 9784 KB Output is correct
9 Correct 196 ms 9776 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 305 ms 9704 KB Output is correct
12 Correct 299 ms 9744 KB Output is correct
13 Correct 298 ms 9864 KB Output is correct
14 Correct 310 ms 9748 KB Output is correct
15 Correct 307 ms 9688 KB Output is correct
16 Correct 296 ms 9788 KB Output is correct
17 Correct 301 ms 9772 KB Output is correct
18 Correct 218 ms 9732 KB Output is correct
19 Correct 211 ms 9816 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct

Subtask #4
0 / 36.0

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

Subtask #5
0 / 28.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 9776 KB Output is correct
2 Correct 209 ms 9796 KB Output is correct
3 Correct 228 ms 9764 KB Output is correct
4 Correct 212 ms 9676 KB Output is correct
5 Correct 207 ms 9776 KB Output is correct
6 Correct 205 ms 9780 KB Output is correct
7 Correct 205 ms 9772 KB Output is correct
8 Correct 211 ms 9784 KB Output is correct
9 Correct 196 ms 9776 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 305 ms 9704 KB Output is correct
12 Correct 299 ms 9744 KB Output is correct
13 Correct 298 ms 9864 KB Output is correct
14 Correct 310 ms 9748 KB Output is correct
15 Correct 307 ms 9688 KB Output is correct
16 Correct 296 ms 9788 KB Output is correct
17 Correct 301 ms 9772 KB Output is correct
18 Correct 218 ms 9732 KB Output is correct
19 Correct 211 ms 9816 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 624 ms 14184 KB Output is correct
22 Correct 546 ms 14156 KB Output is correct
23 Correct 551 ms 14192 KB Output is correct
24 Correct 558 ms 14344 KB Output is correct
25 Correct 576 ms 14168 KB Output is correct
26 Correct 556 ms 14020 KB Output is correct
27 Correct 585 ms 14112 KB Output is correct
28 Correct 336 ms 14232 KB Output is correct
29 Correct 331 ms 14016 KB Output is correct
30 Correct 3 ms 4940 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 150 ms 9760 KB Output is correct
3 Correct 164 ms 9688 KB Output is correct
4 Correct 148 ms 9680 KB Output is correct
5 Correct 149 ms 9672 KB Output is correct
6 Correct 148 ms 9692 KB Output is correct
7 Correct 167 ms 9764 KB Output is correct
8 Correct 157 ms 9760 KB Output is correct
9 Correct 149 ms 9700 KB Output is correct
10 Correct 153 ms 9768 KB Output is correct
11 Correct 219 ms 9776 KB Output is correct
12 Correct 209 ms 9796 KB Output is correct
13 Correct 228 ms 9764 KB Output is correct
14 Correct 212 ms 9676 KB Output is correct
15 Correct 207 ms 9776 KB Output is correct
16 Correct 205 ms 9780 KB Output is correct
17 Correct 205 ms 9772 KB Output is correct
18 Correct 211 ms 9784 KB Output is correct
19 Correct 196 ms 9776 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 305 ms 9704 KB Output is correct
22 Correct 299 ms 9744 KB Output is correct
23 Correct 298 ms 9864 KB Output is correct
24 Correct 310 ms 9748 KB Output is correct
25 Correct 307 ms 9688 KB Output is correct
26 Correct 296 ms 9788 KB Output is correct
27 Correct 301 ms 9772 KB Output is correct
28 Correct 218 ms 9732 KB Output is correct
29 Correct 211 ms 9816 KB Output is correct
30 Correct 3 ms 4940 KB Output is correct
31 Incorrect 4 ms 4940 KB Output isn't correct
32 Halted 0 ms 0 KB -