#include "bits/stdc++.h"
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
find my code templates at https://github.com/galencolin/cp-templates
also maybe subscribe please thanks
*/
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL);}
#define f first
#define s second
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
using ll = long long;
// using ll = int;
// #pragma warning("int")
//
using vl = vector<ll>;
using pl = pair<ll, ll>;
typedef long double ld;
typedef unsigned long long ull;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename num_t>
using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;
// benq - print any container + pair
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
template<typename T> void debug(string s, T x) {cerr << "\033[1;34m" << s << "\033[0;32m = \033[35m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;34m" << s.substr(0, i) << "\033[0;32m = \033[35m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
template<typename T> void debug_nameless(T x) {cerr << "\033[35m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug_nameless(T x, Args... args) {cerr << "\033[35m" << x << "\033[31m | "; debug_nameless(args...);}
#ifdef galen_colin_local
#define pr(...) debug(#__VA_ARGS__, __VA_ARGS__)
#define prs(...) debug_nameless(__VA_ARGS__)
const bool local_ = true;
#else
#define pr(...) 135
#define prs(...) 135
const bool local_ = false;
#endif
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rng(61378913);
/* usage - just do rng() */
void usaco(string filename) {
// #pragma message("be careful, freopen may be wrong")
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
// #include <atcoder/all>
// using namespace atcoder;
const ld pi = 3.14159265358979323846;
// const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
ll n, m, q, k, l, r, x, y, z;
const ll template_array_size = 1e6 + 206171;
ll a[template_array_size];
ll b[template_array_size];
ll c[template_array_size];
string s, t;
ll res(vl c) {
vl a, b;
ll sa = 0, sb = 0;
ll t = 0;
for (ll x: c) {
t += x;
if (sa >= sb) {
b.push_back(x);
sb += x;
} else {
a.push_back(x);
sa += x;
}
}
reverse(b.begin(), b.end());
for (ll x: b) a.push_back(x);
pr(a, t);
ll s = t * (t + 1) / 2, r = 0;
for (ll x: a) r += x, s += r * (t - r);
return s;
}
const bool run = local_ ? 0 : 1;
void solve(int tc = 0) {
cin >> n >> q;
vl a(n);
for (ll &x: a) cin >> x, --x;
for (ll i = 0; i < q; i++) {
cin >> l >> r;
--l; --r;
vl c(n);
for (ll j = l; j <= r; j++) ++c[a[j]];
sort(c.rbegin(), c.rend());
while (c.back() == 0) c.pop_back();
reverse(c.begin(), c.end());
cout << res(c) << '\n';
}
}
int main() {
#ifdef galen_colin_local
auto begin = std::chrono::high_resolution_clock::now();
#endif
send help
#ifndef galen_colin_local
// usaco("evacuation");
#endif
// usaco("cowland");
// freopen("tc.cpp", "r", stdin);
// freopen("tc.cpp", "w", stdout);
// freopen("tc2.cpp", "w", stdout);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
cout << setprecision(15) << fixed;
cerr << setprecision(4) << fixed;
int tc = 1;
// if (local_)
// if (!run)
// cin >> tc;
for (int t = 0; t < tc; t++) {
pr(t); prs(string(50, '-'));
solve(t);
prs(string(50, '-') + "\n");
}
#ifdef galen_colin_local
auto end = std::chrono::high_resolution_clock::now();
cerr << setprecision(4) << fixed;
cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
#endif
}
Compilation message
diversity.cpp:39:44: error: 'void_t' was not declared in this scope
39 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
| ^~~~~~
diversity.cpp:39:44: note: 'std::void_t' is only available from C++17 onwards
diversity.cpp:39:108: error: template argument 2 is invalid
39 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
| ^~
diversity.cpp: In function 'll res(vl)':
diversity.cpp:66:17: warning: statement has no effect [-Wunused-value]
66 | #define pr(...) 135
| ^~~
diversity.cpp:115:5: note: in expansion of macro 'pr'
115 | pr(a, t);
| ^~
diversity.cpp: In function 'int main()':
diversity.cpp:66:17: warning: statement has no effect [-Wunused-value]
66 | #define pr(...) 135
| ^~~
diversity.cpp:169:9: note: in expansion of macro 'pr'
169 | pr(t); prs(string(50, '-'));
| ^~
diversity.cpp:67:18: warning: statement has no effect [-Wunused-value]
67 | #define prs(...) 135
| ^~~
diversity.cpp:169:16: note: in expansion of macro 'prs'
169 | pr(t); prs(string(50, '-'));
| ^~~
diversity.cpp:67:18: warning: statement has no effect [-Wunused-value]
67 | #define prs(...) 135
| ^~~
diversity.cpp:171:9: note: in expansion of macro 'prs'
171 | prs(string(50, '-') + "\n");
| ^~~
diversity.cpp: In function 'void usaco(std::string)':
diversity.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | freopen((filename + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diversity.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen((filename + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
