Submission #1092789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092789		Sunbae	Mountains (NOI20_mountains)	C++17	22 / 100	175 ms	15556 KiB

Mountains

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

Compilation message (stderr)

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

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