oj.uz

Submission #386888

# Submission time Handle Problem Language Result Execution time Memory
386888 2021-04-07T15:24:18 Z fadi57 Mountains (NOI20_mountains) C++14
66 / 100
 536 ms 30220 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mx=4e5+20;
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<ll>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 4 ms 6636 KB Output is correct
2 Correct 536 ms 30060 KB Output is correct
3 Correct 515 ms 30060 KB Output is correct
4 Correct 525 ms 30060 KB Output is correct
5 Correct 515 ms 30060 KB Output is correct
6 Correct 523 ms 30188 KB Output is correct
7 Correct 532 ms 30220 KB Output is correct
8 Correct 515 ms 30092 KB Output is correct
9 Correct 505 ms 21100 KB Output is correct
10 Correct 481 ms 21100 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 11244 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 5 ms 6684 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 6 ms 6636 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6636 KB Output is correct
7 Correct 5 ms 6636 KB Output is correct
8 Correct 7 ms 6636 KB Output is correct
9 Correct 6 ms 6636 KB Output is correct
10 Correct 4 ms 6636 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6684 KB Output is correct
2 Correct 5 ms 6636 KB Output is correct
3 Correct 6 ms 6636 KB Output is correct
4 Correct 5 ms 6636 KB Output is correct
5 Correct 5 ms 6636 KB Output is correct
6 Correct 5 ms 6636 KB Output is correct
7 Correct 5 ms 6636 KB Output is correct
8 Correct 7 ms 6636 KB Output is correct
9 Correct 6 ms 6636 KB Output is correct
10 Correct 4 ms 6636 KB Output is correct
11 Correct 25 ms 7404 KB Output is correct
12 Correct 24 ms 7404 KB Output is correct
13 Correct 23 ms 7404 KB Output is correct
14 Correct 24 ms 7424 KB Output is correct
15 Correct 24 ms 7404 KB Output is correct
16 Correct 25 ms 7404 KB Output is correct
17 Correct 24 ms 7404 KB Output is correct
18 Correct 22 ms 7020 KB Output is correct
19 Correct 17 ms 6764 KB Output is correct
20 Correct 4 ms 6636 KB Output is correct

Subtask #6
0 / 9.0

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

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6636 KB Output is correct
2 Correct 536 ms 30060 KB Output is correct
3 Correct 515 ms 30060 KB Output is correct
4 Correct 525 ms 30060 KB Output is correct
5 Correct 515 ms 30060 KB Output is correct
6 Correct 523 ms 30188 KB Output is correct
7 Correct 532 ms 30220 KB Output is correct
8 Correct 515 ms 30092 KB Output is correct
9 Correct 505 ms 21100 KB Output is correct
10 Correct 481 ms 21100 KB Output is correct
11 Incorrect 181 ms 11244 KB Output isn't correct
12 Halted 0 ms 0 KB -