제출 #752896

#제출 시각아이디문제언어결과실행 시간메모리
752896I_love_Hoang_Yen서열 (APIO23_sequence)C++17
28 / 100
676 ms4184 KiB
#include "sequence.h" #include <bits/stdc++.h> #define SZ(s) ((int) ((s).size())) using namespace std; vector<int> medians(const vector<int> values) { int n = SZ(values); assert(n > 0); if (n % 2 == 0) { return {values[n/2 - 1], values[n / 2]}; } else { return {values[n/2]}; } } int sub1(const vector<int>& a) { int n = SZ(a); int res = 0; for (int l = 0; l < n; ++l) { for (int r = l; r < n; ++r) { vector<int> b(a.begin() + l, a.begin() + r + 1); unordered_map<int, int> cnt; for (int val : b) cnt[val] += 1; sort(b.begin(), b.end()); auto meds = medians(b); for (int med : meds) { res = max(res, cnt[med]); } } } return res; } #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; using namespace __gnu_pbds; int sub2(const vector<int>& a) { int n = SZ(a); int res = 0; for (int l = 0; l < n; ++l) { unordered_map<int, int> cnt; ordered_set values; for (int r = l; r < n; ++r) { cnt[a[r]]++; values.insert(a[r]); int k = SZ(values); if (k % 2 == 0) { res = max(res, cnt[*values.find_by_order(k / 2 - 1)]); res = max(res, cnt[*values.find_by_order(k / 2)]); } else { res = max(res, cnt[*values.find_by_order(k / 2)]); } } } return res; } int sequence(int n, std::vector<int> a) { if (n <= 2000) return sub2(a); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...