Submission #1092543

#TimeUsernameProblemLanguageResultExecution timeMemory
1092543jonghak9028역사적 조사 (JOI14_historical)C++17
100 / 100
1837 ms10688 KiB
/* ************************************************************************** */ /* */ /* ::: ::: ::: */ /* Problem Number: 17731 :+: :+: :+: */ /* +:+ +:+ +:+ */ /* By: js9028 <boj.kr/u/js9028> +#+ +#+ +#+ */ /* +#+ +#+ +#+ */ /* https://boj.kr/17731 #+# #+# #+# */ /* Solved: 2024/09/24 14:38:32 by js9028 ### ### ##.kr */ /* */ /* ************************************************************************** */ #include <bits/stdc++.h> using namespace std; #define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)) typedef long long ll; typedef long double lld; typedef pair<ll, ll> pll; typedef pair<int, int> pii; const int MAXSIZE = 2000000; const long long INF = 1e18 + 5; const double EPSILON = 1e-14; const ll DIV = 2000003; const long double pi = 3.14159265358979323846264338327950288419716939937510L; const int N = 1e5; // limit for array size int n; // array size ll t[2 * N]; void update(int p, ll value) { // set value at position p for (t[p += n] = value; p > 1; p >>= 1) t[p >> 1] = max(t[p], t[p ^ 1]); } ll get(int l, int r) { // sum on interval [l, r) ll res = 0; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) res = max(res, t[l++]); if (r & 1) res = max(res, t[--r]); } return res; } int q; int sq; int idx[100055]; ll arr[100055]; vector<ll> num; vector<array<int, 3>> query; ll ans[100055]; int cnt[100055]; vector<pair<int, int>> mp; void ADD(int i) { i = idx[i]; mp.push_back({i, cnt[i]}); cnt[i]++; } void SUB(int i) { i = idx[i]; mp.push_back({i, cnt[i]}); cnt[i]--; } bool use[100055]; void solve() { int s = 1, e = 0; for (auto [l, r, q] : query) { mp = vector<pair<int, int>>(); while (e < r) e++, ADD(e); while (s > l) s--, ADD(s); while (s < l) SUB(s), s++; while (e > r) SUB(e), e--; for (auto &p : mp) { if (use[p.first]) continue; use[p.first] = 1; update(p.first, num[p.first] * cnt[p.first]); } for (auto &p : mp) { use[p.first] = 0; } ans[q] = get(0, n); } } int main() { fastio; cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> arr[i]; num.push_back(arr[i]); } for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; query.push_back({l, r, i}); } sort(num.begin(), num.end()); for (int i = 1; i <= n; i++) { idx[i] = lower_bound(num.begin(), num.end(), arr[i]) - num.begin(); } sq = sqrt(n); sort(query.begin(), query.end(), [](auto &a, auto &b) { int sa = a[0] / sq, sb = b[0] / sq; if(sa == sb) return a[1] < b[1]; return sa < sb; }); solve(); for (int i = 0; i < q; i++) { cout << ans[i] << "\n"; } 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...