Submission #699874

#TimeUsernameProblemLanguageResultExecution timeMemory
699874bdlSushi (JOI16_sushi)C++17
100 / 100
1950 ms77692 KiB
/* > Statement You are given a circular array A of length N. You are given Q queries, each giving (l, r, a). You are to run the following code: for (int i = l; i <= r; i++) if (a < A[i]) swap(a, A[i]); For each query, output the final value of a. > Scoring 05: 1 <= N, Q <= 2e3 15: For all queries, l = r = 1 80: 1 <= N <= 4e5, 1 <= Q <= 2.5e4, 1 <= A_i <= 1e9 */ #include <iostream> #include <queue> #include <vector> using namespace std; const int N = 4e5, B = 633; struct T { int *a, n; vector<int> u; priority_queue<int> v; void build(int *a_, int n_) { a = a_, n = n_; pull(); } void pull() { v = priority_queue<int>(a, a + n); } int force(int l, int r, int x) { for (int i = l; i <= r; i++) if (x < a[i]) swap(x, a[i]); return x; } int put(int x) { int t = v.top(); if (x < t) { v.pop(); v.push(x); u.push_back(x); x = t; } return x; } void push() { if (u.empty()) return; static priority_queue<int, vector<int>, greater<int>> u_; u_ = priority_queue<int, vector<int>, greater<int>>(u.begin(), u.end()); int t = u_.top(); for (int i = 0; i < n; i++) if (t < a[i]) { u_.pop(), u_.push(a[i]); a[i] = t, t = u_.top(); } u.clear(); } } b[(N - 1) / B + 1]; int update(int l, int r, int x) { if (l / B == r / B) { b[l / B].push(); x = b[l / B].force(l - l / B * B, r - l / B * B, x); b[l / B].pull(); } else { b[l / B].push(); x = b[l / B].force(l - l / B * B, b[l / B].n - 1, x); b[l / B].pull(); for (int i = l / B + 1; i < r / B; i++) x = b[i].put(x); b[r / B].push(); x = b[r / B].force(0, r - r / B * B, x); b[r / B].pull(); } return x; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; static int a[N]; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i <= (n - 1) / B; i++) b[i].build(a + B * i, min(n, B * (i + 1)) - B * i); while (q--) { int l, r, x; cin >> l >> r >> x, l--, r--; if (l <= r) x = update(l, r, x); else { swap(l, r); x = update(r, n - 1, x); x = update(0, l, x); } cout << x << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...