Submission #295385

#	Time	Username	Problem	Language	Result	Execution time	Memory
295385		beso123	Mountains (NOI20_mountains)	C++14	100 / 100	533 ms	20192 KiB

Mountains

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
const int N=300005;
int n,a[N],l[N],r[N];
int bit[N];
int GET(int i){
	int sum=0;
	while(i>=1){
		sum+=bit[i];
		i=i-(i&(-i));
	}
	return sum;
}
void UPD(int i,int val){
	while(i<=n){
		bit[i]+=val;
		i=i+(i&(-i));
	}
}
vector<pii> v;
main(){
cin>>n;
for(int k=1;k<=n;k++)
    cin>>a[k];
for(int k=1;k<=n;k++){
    v.push_back({a[k],k});
}
sort(v.begin(),v.end());
a[v[0].y]=1;
for(int k=1;k<v.size();k++){
    a[v[k].y]=a[v[k-1].y];
    if(v[k].x!=v[k-1].x)
        a[v[k].y]++;
}
UPD(a[1],1);
for(int k=2;k<=n;k++){
    l[k]=GET(a[k]-1);
    UPD(a[k],1);
}
for(int k=1;k<=n;k++)
    bit[k]=0;
    UPD(a[n],1);
for(int k=n-1;k>=1;k--){
    r[k]=GET(a[k]-1);
    UPD(a[k],1);
}
int ans=0;
for(int k=1;k<=n;k++)
    ans+=l[k]*r[k];
cout<<ans;
return 0;
}

Compilation message (stderr)

Mountains.cpp:25:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main(){
      |      ^
Mountains.cpp: In function 'int main()':
Mountains.cpp:34:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 | for(int k=1;k<v.size();k++){
      |             ~^~~~~~~~~
Mountains.cpp:44:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   44 | for(int k=1;k<=n;k++)
      | ^~~
Mountains.cpp:46:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   46 |     UPD(a[n],1);
      |     ^~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 9 / 9
• Subtask 7: 12 / 12