Submission #1248135

#TimeUsernameProblemLanguageResultExecution timeMemory
1248135orzngaihaPilot (NOI19_pilot)C++20
40 / 100
38 ms9288 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, q, ans[N]; pair<int, int> a[N], b[N]; struct Node { int L, R, len; long long sum; } st[4 * N]; Node merge(Node a, Node b) { Node res; res.len = a.len + b.len; res.L = (a.L == a.len) ? a.len + b.L : a.L; res.R = (b.R == b.len) ? b.len + a.R : b.R; res.sum = a.sum + b.sum + 1LL * a.R * b.L; return res; } void build(int id, int l, int r) { st[id] = {0, 0, r - l + 1, 0}; if (l == r) return; int mid = (l + r) / 2; build(2 * id, l, mid); build(2 * id + 1, mid + 1, r); } void update(int id, int l, int r, int i) { if (i < l || i > r) return; if (l == r) { st[id] = {1, 1, 1, 1}; return; } int mid = (l + r) / 2; update(2 * id, l, mid, i); update(2 * id + 1, mid + 1, r, i); st[id] = merge(st[2 * id], st[2 * id + 1]); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> a[i].first; a[i].second = i; } for (int i = 1; i <= q; i++) { cin >> b[i].first; b[i].second = i; } sort(a + 1, a + n + 1); sort(b + 1, b + q + 1); build(1, 1, n); int l = 1; for (int i = 1; i <= q; i++) { while (l <= n && a[l].first <= b[i].first) { update(1, 1, n, a[l].second); l++; } ans[b[i].second] = st[1].sum; } 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...
#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...