oj.uz

Submission #386880

# Submission time Handle Problem Language Result Execution time Memory
386880 2021-04-07T15:16:30 Z fadi57 Mountains (NOI20_mountains) C++14
2 / 100
 175 ms 9084 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mx=3e5;
const int mod= 1e9+7 ;
const ll inf=1e9+5;

//***while there is life there is hope
int n;

int arr[mx*4];



map<ll,int>mp;

void compres(){
int cnt=0;
for(auto &it:mp){
        //cout<<it.first;
    it.second=cnt;
    cnt++;
}

}
void update(int node,int st,int en,int pos){


if(st==en){
    arr[node]++;
    return;
}
int mid=(st+en)/2;

if(pos<=mid){
    update(node*2,st,mid,pos);
}else{
 update(node*2+1,mid+1,en,pos);
 }
 arr[node]=arr[node*2]+arr[node*2+1];return ;



}
int query(int node,int st,int en,int l,int r){

if(st>r||en<l){return 0;}

if(st>=l&&en<=r){return arr[node];}
int mid=(st+en)/2;
return query(node*2,st,mid,l,r)+query(node*2+1,mid+1,en,l,r);


}
int l[mx];int r[mx];
int main() {
cin>>n;
vector<int>v(n);
for(int i=0;i<n;i++){


   cin>>v[i];
  mp[v[i]];
}
compres();
for(int i=0;i<n;i++){


    v[i]=mp[v[i]];
   // cout<<v[i];
}

for(int i=0;i<n;i++){
    l[i]=query(1,0,mx,0,v[i]-1);
   // cout<<l[i]<<" ";
    update(1,0,mx,v[i]);
}
memset(arr,0,sizeof(arr));ll ans=0;
for(int i=n-1;i>=0;i--){
    r[i]=query(1,0,mx,0,v[i]-1);
    //cout<<r[i]<<" ";
    update(1,0,mx,v[i]);
    ans+=r[i]*l[i];
}cout<<ans;

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 87 ms 8556 KB Output is correct
3 Correct 88 ms 8556 KB Output is correct
4 Correct 87 ms 8612 KB Output is correct
5 Correct 100 ms 8556 KB Output is correct
6 Correct 96 ms 8528 KB Output is correct
7 Correct 88 ms 8704 KB Output is correct
8 Correct 90 ms 8592 KB Output is correct
9 Correct 87 ms 8556 KB Output is correct
10 Correct 89 ms 8616 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4972 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 4972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

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

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 87 ms 8556 KB Output is correct
3 Correct 88 ms 8556 KB Output is correct
4 Correct 87 ms 8612 KB Output is correct
5 Correct 100 ms 8556 KB Output is correct
6 Correct 96 ms 8528 KB Output is correct
7 Correct 88 ms 8704 KB Output is correct
8 Correct 90 ms 8592 KB Output is correct
9 Correct 87 ms 8556 KB Output is correct
10 Correct 89 ms 8616 KB Output is correct
11 Incorrect 175 ms 9084 KB Output isn't correct
12 Halted 0 ms 0 KB -