oj.uz

답안 #386881

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386881 2021-04-07T15:18:42 Z fadi57 Mountains (NOI20_mountains) C++14
66 / 100
 531 ms 34284 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<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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 508 ms 34156 KB Output is correct
3 Correct 513 ms 33964 KB Output is correct
4 Correct 514 ms 34028 KB Output is correct
5 Correct 512 ms 34028 KB Output is correct
6 Correct 514 ms 34284 KB Output is correct
7 Correct 524 ms 34156 KB Output is correct
8 Correct 531 ms 34156 KB Output is correct
9 Correct 476 ms 25100 KB Output is correct
10 Correct 472 ms 25096 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 178 ms 10220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 178 ms 10220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct

Subtask #5
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct
11 Correct 23 ms 5996 KB Output is correct
12 Correct 23 ms 5996 KB Output is correct
13 Correct 23 ms 5996 KB Output is correct
14 Correct 23 ms 5996 KB Output is correct
15 Correct 23 ms 5996 KB Output is correct
16 Correct 23 ms 5996 KB Output is correct
17 Correct 22 ms 5996 KB Output is correct
18 Correct 22 ms 5632 KB Output is correct
19 Correct 14 ms 5228 KB Output is correct
20 Correct 3 ms 4972 KB Output is correct

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 178 ms 10220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 508 ms 34156 KB Output is correct
3 Correct 513 ms 33964 KB Output is correct
4 Correct 514 ms 34028 KB Output is correct
5 Correct 512 ms 34028 KB Output is correct
6 Correct 514 ms 34284 KB Output is correct
7 Correct 524 ms 34156 KB Output is correct
8 Correct 531 ms 34156 KB Output is correct
9 Correct 476 ms 25100 KB Output is correct
10 Correct 472 ms 25096 KB Output is correct
11 Incorrect 178 ms 10220 KB Output isn't correct
12 Halted 0 ms 0 KB -