Submission #927633

#TimeUsernameProblemLanguageResultExecution timeMemory
927633galen_colinDiversity (CEOI21_diversity)C++17
64 / 100
7061 ms12280 KiB
#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 (stderr)

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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...