oj.uz

Submission #227169

# Submission time Handle Problem Language Result Execution time Memory
227169 2020-04-26T09:56:22 Z TheKingAleks Mountains (NOI20_mountains) C++14
2 / 100
 52 ms 9208 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAX_N = 3e5+2;
int a[MAX_N];
int res;
set<int> s;
unordered_map<int,int> m;
int br=1;
vector<int> tree1(MAX_N*2);
vector<int> tree2(MAX_N*2);
void update(vector<int> &tree,int node,int tl,int tr,int l,int r)
{
    if(tl > r || tr < l)return;
    if(tl == tr)
    {
        tree[node]++;
        return;
    }
    int mid = (tl+tr)/2;
    update(tree,node*2,tl,mid,l,r);
    update(tree,node*2+1,mid+1,tr,l,r);
    tree[node] = tree[node*2]+tree[node*2+1];
}
int query(vector<int> &tree,int node,int tl,int tr,int l,int r)
{
    if(tl > r || tr < l)return 0;
    if(tl >= l && tr <= r)
    {
        return tree[node];
    }
    int mid = (tl+tr)/2;
    return query(tree,node*2,tl,mid,l,r)+query(tree,node*2+1,mid+1,tr,l,r);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    vector<int> l(n);
    vector<int> r(n);
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        s.insert(a[i]);
    }
    for(auto &it : s)
    {
        m[it] = br;
        br++;
    }
    br--;
    update(tree1,1,1,br,m[a[0]],m[a[0]]);
    for(int i=1; i<n; i++)
    {
        l[i] = query(tree1,1,1,br,1,m[a[i]]-1);
        update(tree1,1,1,br,m[a[i]],m[a[i]]);
    }
    update(tree2,1,1,br,m[a[n-1]],m[a[n-1]]);
    for(int i=n-2; i>=0; i--)
    {
        r[i] = query(tree2,1,1,br,1,m[a[i]]-1);
        update(tree2,1,1,br,m[a[i]],m[a[i]]);
    }
    for(int i=0;i<n;i++)
    {
        res+=(l[i]*r[i]);
    }
    cout<<res<<endl;

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 31 ms 7424 KB Output is correct
3 Correct 29 ms 7424 KB Output is correct
4 Correct 27 ms 7424 KB Output is correct
5 Correct 29 ms 7424 KB Output is correct
6 Correct 29 ms 7424 KB Output is correct
7 Correct 28 ms 7424 KB Output is correct
8 Correct 30 ms 7424 KB Output is correct
9 Correct 30 ms 7424 KB Output is correct
10 Correct 28 ms 7424 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 36.0

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

Subtask #5
0 / 28.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 31 ms 7424 KB Output is correct
3 Correct 29 ms 7424 KB Output is correct
4 Correct 27 ms 7424 KB Output is correct
5 Correct 29 ms 7424 KB Output is correct
6 Correct 29 ms 7424 KB Output is correct
7 Correct 28 ms 7424 KB Output is correct
8 Correct 30 ms 7424 KB Output is correct
9 Correct 30 ms 7424 KB Output is correct
10 Correct 28 ms 7424 KB Output is correct
11 Incorrect 52 ms 9208 KB Output isn't correct
12 Halted 0 ms 0 KB -