Submission #835791

#TimeUsernameProblemLanguageResultExecution timeMemory
835791VMaksimoski008Mountains (NOI20_mountains)C++14
66 / 100
275 ms41184 KiB
#include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define uniq(x) x.erase(unique(all(x)), x.end()) #define rall(x) x.rbegin(), x.rend() //#define int long long using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; const double eps = 1e-9; void setIO() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } struct SegTree { int n; vector<int> tree; SegTree(int n) : n(n), tree(4*n+5) {} void update(int u, int tl, int tr, int pos, int val) { if(tl == tr) { tree[u] += val; } else { int tm = (tl + tr) / 2; if(pos <= tm) update(2*u, tl, tm, pos, val); else update(2*u+1, tm+1, tr, pos, val); tree[u] = tree[2*u] + tree[2*u+1]; } } int query(int u, int tl, int tr, int l, int r) { if(tl > tr || l > tr || tl > r) return 0; if(l <= tl && tr <= r) return tree[u]; int tm = (tl + tr) / 2; return query(2*u, tl, tm, l, r) + query(2*u+1, tm+1, tr, l, r); } void update(int pos, int val) { update(1, 0, n-1, pos, val); } int query(int l, int r) { return query(1, 0, n-1, l, r); } }; int32_t main() { setIO(); int n; cin >> n; vector<ll> v(n); for(ll &x : v) cin >> x; vector<ll> tmp(v); map<ll, int> key; sort(all(tmp)); uniq(tmp); for(int i=0; i<tmp.size(); i++) key[tmp[i]] = i; vector<int> dp_left(n), dp_right(n); SegTree tree_left(tmp.size()); SegTree tree_right(tmp.size()); //calc dp left for(int i=0; i<n; i++) { int pos = key[v[i]]; dp_left[i] = tree_left.query(0, pos-1); tree_left.update(pos, 1); } for(int i=n-1; i>=0; i--) { int pos = key[v[i]]; dp_right[i] = tree_right.query(0, pos-1); tree_right.update(pos, 1); } ll ans = 0; for(int i=0; i<n; i++) ans += 1ll * (dp_left[i] * dp_right[i]); cout << '\n'; cout << ans << '\n'; return 0; }

Compilation message (stderr)

Mountains.cpp: In function 'int32_t main()':
Mountains.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0; i<tmp.size(); i++)
      |                  ~^~~~~~~~~~~
#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...