Submission #617065

#TimeUsernameProblemLanguageResultExecution timeMemory
617065dxz05Diversity (CEOI21_diversity)C++14
4 / 100
7087 ms1828 KiB
//#pragma GCC optimize("Ofast,O2,O3,unroll-loops") //#pragma GCC target("avx2") #include <bits/stdc++.h> using namespace std; void debug_out() { cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << "[" << H << "]"; debug_out(T...); } #ifdef dddxxz #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif #define SZ(s) ((int)s.size()) #define all(x) (x).begin(), (x).end() #define lla(x) (x).rbegin(), (x).rend() #define bpc(x) __builtin_popcount(x) #define bpcll(x) __builtin_popcountll(x) #define MP make_pair clock_t startTime; double getCurrentTime() { return (double) (clock() - startTime) / CLOCKS_PER_SEC; } mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); typedef long long ll; const int MOD = 998244353; const int INF = 1000000101; const long long LLINF = 1223372000000000555; const int N = 1e6 + 3e2; const int M = 1555; int diversity(vector<int> a){ int n = (int)a.size(); int res = 0; for (int i = 0; i < n; i++){ set<int> s; for (int j = i; j < n; j++){ s.insert(a[j]); res += (int)s.size(); } } return res; } void solve(int TC) { int n, q; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int m = *max_element(all(a)) + 1; vector<int> cnt(m, 0); while (q--){ int l, r; cin >> l >> r; --l, --r; for (int i = l; i <= r; i++) cnt[a[i]]++; set<pair<int, int>> s; for (int i = l; i <= r; i++){ s.insert(MP(cnt[a[i]], a[i])); } deque<int> dq; int flag = 0; while (!s.empty()){ int x = s.rbegin()->second; s.erase(*s.rbegin()); if (flag) dq.push_back(x); else dq.push_front(x); flag ^= 1; } vector<int> b; for (int x : dq){ while (cnt[x]--) b.push_back(x); } // for (int x : b) cout << x << ' '; cout << diversity(b) << endl; } } int main() { startTime = clock(); ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifdef dddxxz freopen("input.txt", "rg", stdin); freopen("output.txt", "w", stdout); #endif int TC = 1; //cin >> TC; for (int test = 1; test <= TC; test++) { //debug(test); //cout << "Case #" << test << ": "; solve(test); } #ifdef dddxxz cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl; #endif return 0; }
#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...