oj.uz

Submission #335602

# Submission time Handle Problem Language Result Execution time Memory
335602 2020-12-13T09:07:58 Z beepbeepsheep Mountains (NOI20_mountains) C++17
0 / 100
 43 ms 25580 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
vector<int> tree[400020];
const int inf=2e9;
int arr[100005];
void build(int node,int s,int e){
    if (s==e){
        tree[node].emplace_back(arr[s]);
        return;
    }
    int m=(s+e)/2;
    int left=node<<1;
    int right=left|1;
    build(left,s,m);
    build(right,m+1,e);
    merge(tree[left].begin(),tree[left].end(),tree[right].begin(),tree[right].end(),back_inserter(tree[node]));
}
int query(int node,int l,int r,int i,int j,int k){
    if (i>r||j<l) return 0;
    if (i<=l && r<=j) return lower_bound(tree[node].begin(),tree[node].end(),k)-tree[node].begin();
    int mid=(l+r)/2;
    int left=node<<1;
    int right=left|1;
    return query(left,l,mid,i,j,k)+query(right,mid+1,r,i,j,k);

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
    cin>>n;
    pair<int,int> num[n];
    for (int i=0;i<n;i++){
        cin>>num[i].first;
        arr[i]=num[i].first;
        num[i].second=i;
    }
    int a,b;
    ll ans=0;
    build(1,0,n-1);
    for (int i=0;i<n;i++){
        a=query(1,0,n-1,num[i].second,n-1,num[i].first);
        b=query(1,0,n-1,0,num[i].second,num[i].first);
        ans+=a*b;
    }
    cout<<ans;
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Runtime error 26 ms 25068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 25580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 25580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

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

Subtask #5
0 / 28.0

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

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 25580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Runtime error 26 ms 25068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -