Submission #439077

#TimeUsernameProblemLanguageResultExecution timeMemory
439077skybergMountains (NOI20_mountains)C++17
2 / 100
7 ms9676 KiB
#include <iostream> #include <vector> #include <cstring> #include <algorithm> #include <map> using namespace std; long long int t[1200000]; long long int g[300000]; long long int left1[300000], right1[300000]; void update (int v, int tl, int tr, int h) { if (tl == tr) t[v]++; else { int tm = (tl + tr) / 2; if (h <= tm) update (v*2, tl, tm, h); else update (v*2+1, tm+1, tr, h); t[v] = t[v*2] + t[v*2+1]; } } int sum (int v, int tl, int tr, int l, int r) { if (l > r) return 0; if (l == tl && r == tr) return t[v]; int tm = (tl + tr) / 2; return sum (v*2, tl, tm, l, min(r,tm)) + sum (v*2+1, tm+1, tr, max(l,tm+1), r); } int main(){ int n; freopen("13.in.txt", "r", stdin); cin >> n; vector<long long int>b; for(int i = 0; i < n; i++){ cin >> g[i]; b.push_back(g[i]); } sort(b.begin(), b.end()); map<long long int,long long int>c; for(int i = 0; i < b.size(); i++){ c[b[i]] = i; } for(int i = 0; i < n; i++){ g[i] = c[g[i]]; } update(1, 0, n, g[0]); for(int i = 1; i < n - 1; i++){ left1[i] = sum(1, 0, n, 0, g[i] - 1); update(1, 0, n, g[i]); } memset(t, 0, sizeof(t[0]) * 1200000); update(1, 0, n, g[n - 1]); for(int i = n - 2; i >= 1; i--){ right1[i] = sum(1, 0, n, 0, g[i] - 1); update(1, 0, n, g[i]); } long long int ans = 0; for(int i = 1; i < n - 1; i++){ ans += 1LL * left1[i] * right1[i]; } cout << ans; return 0; }

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < b.size(); i++){
      |                    ~~^~~~~~~~~~
Mountains.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen("13.in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...