?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
192035586 |
Practice: hydra_cody |
459D - 58 | C++17 (GCC 7-32) | Time limit exceeded on test 17 | 3000 ms | 94216 KB | 2023-02-03 19:57:48 | 2023-02-03 19:57:54 |
#include<bits/stdc++.h> using namespace std; // #include "atcoder/math.hpp" // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define endl "\n" #define pb push_back #define pf push_front #define pob pop_back #define pof pop_front #define mp make_pair #define fi first #define se second #define set_bits __builtin_popcountll #define precise(ans) cout<<fixed<<setprecision(15)<<ans #define fo(i,n) for(ll i=0;i<n;i++) #define Fo(i,k,n) for(ll i=k;k<n?i<n:i>n;k<n?i+=1:i-=1) #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++) #define sz(x) ((ll)(x).size()) #define all(x) x.begin(), x.end() #define clr(x) memset(x, 0, sizeof(x)) #define yes cout << "YES" << endl; #define no cout << "NO" << endl; #define case cout<<"Case #"<<i<<": "; #define PI 3.1415926535897932384626 #define MOD 1000000007 #define MOD1 998244353 typedef long long ll; typedef unsigned long long ull; typedef long double lld; typedef pair<ll, ll> pii; typedef pair<ll, ll> pl; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<pii> vpii; typedef vector<pl> vpl; template <typename T> using prq_mx = priority_queue<T>; template <typename T> using prq_mn = priority_queue<T, vector<T>, greater<T>>; const double eps = 1e-9; const ll INF = (ll) 1e9; const ll inf64 = 2e18; const ll INF64 = 9e18; // template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // template <class K, class V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>; #ifndef ONLINE_JUDGE #define debug(x) cerr << #x <<" "; _prll(x); cerr << endl; #else #define debug(x) #endif // void _prll(ll t) {cerr << t;} void _print(ll t) {cerr << t;} void _prll(string t) {cerr << t;} void _prll(char t) {cerr << t;} void _prll(lld t) {cerr << t;} void _prll(double t) {cerr << t;} void _prll(ull t) {cerr << t;} template <class T, class V> void _prll(pair <T, V> p); template <class T> void _prll(vector <T> v); template <class T> void _prll(set <T> v); template <class T, class V> void _prll(map <T, V> v); template <class T> void _prll(multiset <T> v); template <class T, class V> void _prll(pair <T, V> p) {cerr << "{"; _prll(p.fi); cerr << ","; _prll(p.se); cerr << "}";} template <class T> void _prll(vector <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";} template <class T> void _prll(set <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";} template <class T> void _prll(multiset <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";} template <class T, class V> void _prll(map <T, V> v) {cerr << "[ "; for (auto i : v) {_prll(i); cerr << " ";} cerr << "]";} //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ll n; vector<ll> bit; void update(ll k,ll val) { while(k<=n) { bit[k]+=val; k+=(k&(-k)); } } ll sum(ll k) { ll res=0; while(k>0) { res+=bit[k]; k-=(k&(-k)); } return res; } ll query(ll l,ll r) { return sum(r)-sum(l-1); } void chal() { cin>>n; vector<ll> aa(n); bit.resize(n+1,0); map<ll,ll> bb,cc; fo(i,n){ cin>>aa[i]; bb[aa[i]]++; update(bb[aa[i]],1); } ll ans=0; fo(i,n){ update(bb[aa[i]],-1); bb[aa[i]]--; cc[aa[i]]++; ans+=query(1,cc[aa[i]]-1); // cout<<query(cc[aa[i]]-1,1)<<' '; } cout<<ans<<endl; } //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); srand(chrono::high_resolution_clock::now().time_since_epoch().count()); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("Error.txt", "w", stderr); #endif ll t; t = 1; // cin >> t; for (ll i = 1; i <= t; i++) {chal();} return 0; }
?
?
?
?