Submission #224517

#	Time	Username	Problem	Language	Result	Execution time	Memory
224517		Nightlight	Mountains (NOI20_mountains)	C++14	100 / 100	938 ms	48276 KiB

Mountains

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp> 
#define pii pair<long long, int>
using namespace std;
using namespace __gnu_pbds;

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N;
long long A[300005];
long long L[300005];
long long ans;
ordered_set suf, pre;

int main() {
  scanf("%d", &N);
  for(int i = 1; i <= N; i++) {
    scanf("%lld", &A[i]);
    L[i] = pre.order_of_key({A[i], 0});
    pre.insert({A[i], i});
  }
  long long R;
  for(int i = N; i > 0; i--) {
    R = suf.order_of_key({A[i], i});
    ans += R * L[i];
    suf.insert({A[i], i});
  }
  printf("%lld\n", ans);
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
Mountains.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &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