Submission #1092794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092794		Sunbae	Mountains (NOI20_mountains)	C++17	100 / 100	160 ms	14188 KiB

Mountains

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 3e5 + 5;
ll a[N], cp[N], A[N], tot;
int m, n, bit[N];
int qry(int i){ int r = 0; for(; i; i-=i&-i) r += bit[i]; return r;}
void upd(int i){ for(; i<=m; i+=i&-i) ++bit[i];}
int pos(ll x){ return upper_bound(cp, cp+m, x) - cp;}
signed main(){
	scanf("%d", &n); for(int i = 0; i<n; ++i) scanf("%lld", a+i), cp[m++] = a[i];
	sort(cp, cp+m); m = unique(cp, cp+m) - cp;
	for(int i = 0, j; i<n; ++i) A[i] = qry((j = pos(a[i]))-1), upd(j);
	memset(bit, 0, sizeof(bit));
	for(int i = n-1, j; i>=0; --i) tot += A[i] *= qry((j = pos(a[i]))-1), upd(j);
	printf("%lld", tot);
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d", &n); for(int i = 0; i<n; ++i) scanf("%lld", a+i), cp[m++] = a[i];
      |  ~~~~~^~~~~~~~~~
Mountains.cpp:11:49: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d", &n); for(int i = 0; i<n; ++i) scanf("%lld", a+i), cp[m++] = a[i];
      |                                            ~~~~~^~~~~~~~~~~~~

• 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