Submission #447353

#TimeUsernameProblemLanguageResultExecution timeMemory
447353jhwest2역사적 조사 (JOI14_historical)C++17
40 / 100
4082 ms11444 KiB
#include <bits/stdc++.h> #define va first #define vb second using namespace std; typedef long long lint; typedef pair<int, int> pint; const int M = 1e5 + 10, SQ = 400; int n, q, A[M], Count[M]; lint Ans[M]; pair<pint, int> Qry[M]; vector<lint> V; struct Set { multiset<lint> St; void insert(lint x) { St.erase(St.find(Count[x] * V[x])); Count[x] += 1; St.insert(Count[x] * V[x]); } void erase(lint x) { St.erase(St.find(Count[x] * V[x])); Count[x] -= 1; St.insert(Count[x] * V[x]); } lint query() { return *prev(St.end()); } } St; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> A[i]; V.push_back(A[i]); } sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end()); for (int i = 1; i <= n; i++) { A[i] = lower_bound(V.begin(), V.end(), A[i]) - V.begin(); } for (int i = 1; i <= q; i++) { cin >> Qry[i].va.va >> Qry[i].va.vb; Qry[i].vb = i; } stable_sort(Qry + 1, Qry + 1 + q, [&](auto a, auto b) { if (a.va.va / SQ == b.va.va / SQ) return a.va.vb <= b.va.vb; return a.va.va <= b.va.va; }); for (int i = 1; i <= n; i++) St.St.insert(0); int l = 1, r = 0; for (int i = 1; i <= q; i++) { while (Qry[i].va.vb > r) St.insert(A[++r]); while (Qry[i].va.vb < r) St.erase(A[r--]); while (Qry[i].va.va > l) St.erase(A[l++]); while (Qry[i].va.va < l) St.insert(A[--l]); Ans[Qry[i].vb] = St.query(); } for (int i = 1; i <= q; i++) { cout << Ans[i] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...