Submission #760368

#TimeUsernameProblemLanguageResultExecution timeMemory
760368Sam_a17Diversity (CEOI21_diversity)C++17
18 / 100
56 ms5040 KiB
/// #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> //#include "temp.cpp" #include <cstdio> using namespace std; #ifndef ONLINE_JUDGE #define dbg(x) cerr << #x <<" "; print(x); cerr << endl; #else #define dbg(x) #endif #define sz(x) (int)x.size() #define len(x) (int)x.length() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(x) (x).clear() #define uniq(x) x.resize(unique(all(x)) - x.begin()); #define blt __builtin_popcount #define pb push_back #define popf pop_front #define popb pop_back #define ld long double void print(long long t) {cerr << t;} void print(int t) {cerr << t;} void print(string t) {cerr << t;} void print(char t) {cerr << t;} void print(double t) {cerr << t;} void print(long double t) {cerr << t;} void print(unsigned long long t) {cerr << t;} template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";} template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";} template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // for random generations // mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); mt19937 myrand(373); // for grid problems int dx[8] = {-1,0,1,0,1,-1,1,-1}; int dy[8] = {0,1,0,-1,1,1,-1,-1}; // lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6 void fastIO() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } // file in/out void setIO(string str = "") { fastIO(); if(str == "input") { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } else { // freopen("skis.in", "r", stdin); // freopen("skis.out", "w", stdout); } } // Indexed Set template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 4e5 + 10; struct query { long long l, r, ind; }; long long n, q, a[N], s = 600, qar[N]; long long ans[N]; vector<query> queries; bool cmp(query a, query b) { if(a.l / s ^ b.l / s) { return a.l / s < b.l / s; } return a.r > b.r; } long long cur[N]; map<long long, long long> mp; void add(int ind) { if(cur[a[ind]]) { mp[cur[a[ind]]]--; if(!mp[cur[a[ind]]]) { mp.erase(cur[a[ind]]); } } cur[a[ind]]++; mp[cur[a[ind]]]++; } void del(int ind) { mp[cur[a[ind]]]--; if(!mp[cur[a[ind]]]) { mp.erase(cur[a[ind]]); } cur[a[ind]]--; if(cur[a[ind]]) mp[cur[a[ind]]]++; } long long pre(long long x) { return x * (x + 1) / 2; } long long get(long long all) { vector<pair<long long, long long>> vec; for(auto i: mp) { if(i.second) { vec.push_back({i.first, i.second}); } } vector<pair<long long, long long>> lef, rig; long long l = 0, r = 0; for(auto i: vec) { if(l == r) { if(i.second % 2 == 1) { l += (i.second + 1) / 2; r += i.second / 2; lef.push_back({i.first, (i.second + 1) / 2}); if(i.second / 2) rig.push_back({i.first, i.second / 2}); } else { l += i.second / 2; r += i.second / 2; if(i.second / 2) lef.push_back({i.first, i.second / 2}); if(i.second / 2) rig.push_back({i.first, i.second / 2}); } } else if(l > r) { if(i.second % 2 == 1) { l += i.second / 2; r += (i.second + 1) / 2; if(i.second / 2) lef.push_back({i.first, i.second / 2}); rig.push_back({i.first, (i.second + 1) / 2}); } else { l += i.second / 2; r += i.second / 2; if(i.second / 2) lef.push_back({i.first, i.second / 2}); if(i.second / 2) rig.push_back({i.first, i.second / 2}); } } else if(l < r) { assert(false); } } vector<pair<long long, long long>> curr; for(auto i: lef) { curr.push_back(i); } reverse(all(rig)); for(auto i: rig) { curr.push_back(i); } long long ans = 0; // for each block for(auto i: vec) { ans += i.second * (i.first * (i.first + 1) / 2); } long long x = 0; for(auto i: curr) { long long y = all - x - i.first * i.second; //..x...CUR...y... // for(long long j = 0; j < i.second; j++) { // long long cx = x + j * i.first; // long long cy = y + (i.second - j - 1) * i.first; // ans += cx * cy; // } ans += i.second * x * y; ans += i.first * y * pre(i.second - 1); ans += i.first * x * pre(i.second - 1); // dbg(i.second) // dbg(i.first) // dbg(ans) for(long long j = 1; j < i.second; j++) { ans += i.first * i.first * (j * (i.second - j)); } // dbg(ans) // ans += i.second * x * i.first; ans += i.first * i.first * pre(i.second - 1); ans += i.second * y * i.first; ans += i.first * i.first * pre(i.second - 1); x += i.first * i.second; } return ans; } void solve_() { int n, q; cin >> n >> q; for(int i = 0; i < n; i++) { cin >> a[i]; } for(long long i = 1; i <= n; i++) { qar[i] = qar[i - 1] + i * i; } for(int i = 0; i < q; i++) { int a,b; cin >> a >> b; queries.push_back({--a, b, i}); } sort(queries.begin(), queries.end(), cmp); int l = 0, r = 0; for(int i = 0; i < q; i++) { int currL = queries[i].l, currR = queries[i].r, idx = queries[i].ind; while(r < currR) { add(r++); } while(l > currL) { add(--l); } while(r > currR) { del(--r); } while(l < currL) { del(l++); } ans[idx] = get(currR - currL); } for(int i = 0; i < q; i++) { cout << ans[i] << '\n'; } } int main() { setIO(); auto solve = [&](int test_case)-> void { for(int i = 1; i <= test_case; i++) { solve_(); } }; int test_cases = 1; // cin >> test_cases; solve(test_cases); return 0; }

Compilation message (stderr)

diversity.cpp: In function 'void setIO(std::string)':
diversity.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
diversity.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen("output.txt", "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...