Submission #1190986

#TimeUsernameProblemLanguageResultExecution timeMemory
1190986AliyyiakbarMountains (NOI20_mountains)C++20
0 / 100
13 ms1164 KiB
/* #ifndef ONLINE_JUDGE #include "AkbarKING.h" #else #define debug(...) #define debugArr(...) #define debugG(...) #endif */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/hash_policy.hpp> #define int long long #define $AzH_TxdmN$ ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr); /* #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") #pragma GCC optimize("Ofast") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("fast-math") */ /* #define NaxcivanlilaraEkranKaydiAlmayaSonOnlardaInsanKimiKocureBilerlerVeSecmedeGCD100LeyeBilerler dp[1][1]; #define Aliyyakbar dp[i][j] #define MirrehimM dp[0][0] #define Xanlar dp[i-1][j] #define Elay dp[i][j-1] #define Rufo dp[i-1][j-1] #define Yusif dp[i+1][j] #define Sayad dp[i][j+1] #define Sumuraz dp[i+1][j+1] #define Cebrayil dp[i+1][j-1] #define Riyad dp[n][m] #define Huseyn dp[n-1][m] #define Zako dp[n][m-1] #define Abdulla dp[n-1][m-1] #define Subhan dp[n+1][m] #define Others dp[i-1][j+1] */ #define ep emplace_back #define pb push_back #define pii pair<int,int> #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() using namespace std; using namespace __gnu_pbds; template <typename T> using __indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T> using __indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count()); const int sz = 1e5 + 9; const int LOG = 63; const int MOD = 1e9 + 7; const int INF = 1e18; int a[sz], t[2][sz << 2]; int n; void update(int mask, int node, int l, int r, int pos, int val) { if (l == r) { t[mask][node] += val; return; } int mid = (l + r) >> 1; if (pos <= mid) { update(mask, node << 1, l, mid, pos, val); } else { update(mask, node << 1 | 1, mid + 1, r, pos, val); } t[mask][node] = t[mask][node << 1] + t[mask][node << 1 | 1]; } int get(int mask, int node, int l, int r, int ql, int qr) { if (l > qr || r < ql) { return 0; } if (ql <= l && r <= qr) { return t[mask][node]; } int mid = (l + r) >> 1; return get(mask, node << 1, l, mid, ql, qr) + get(mask, node << 1 | 1, mid + 1, r, ql, qr); } void solve() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; update(1, 1, 0, 1e5, a[i], +1); } int res = 0; update(0, 1, 0, 1e5, a[1], +1); update(1, 1, 0, 1e5, a[1], -1); for (int i = 2; i < n; ++i) { /// debug(get(0, 1, 0, 1e5, 0, a[i] - 1), get(1, 1, 0, 1e5, 0, a[i] - 1)); res += get(0, 1, 0, 1e5, 0, a[i] - 1) * get(1, 1, 0, 1e5, 0, a[i] - 1); update(0, 1, 0, 1e5, a[i], +1); update(1, 1, 0, 1e5, a[i], -1); } cout << res << '\n'; } signed main() { $AzH_TxdmN$ int t = 1; // cin >> t; while (t--) { solve(); } }
#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...