제출 #699882

#제출 시각아이디문제언어결과실행 시간메모리
699882bdlSushi (JOI16_sushi)C++17
100 / 100
2172 ms51984 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 = 1000; char _buf[1 << 20], *_p1, *_p2; #define getchar() (_p1 == _p2 ? (_p2 = _buf + fread(_p1 = _buf, 1, 1 << 20, stdin), _p1 == _p2 ? EOF : *_p1++) : *_p1++) int read() { int s = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); } while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar(); return s * w; } 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 main() { int n = read(), q = read(); static int a[N]; for (int i = 0; i < n; i++) a[i] = read(); 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 = read() - 1, r = read() - 1, x = read(); if (l <= r) { 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(); } } else { if (l / B == r / B) { b[l / B].push(); x = b[l / B].force(l - l / B * B, b[l / B].n - 1, x); for (int i = l / B + 1; i <= (n - 1) / B; i++) x = b[i].put(x); for (int i = 0; i < l / B; i++) x = b[i].put(x); x = b[l / B].force(0, 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 <= (n - 1) / B; i++) x = b[i].put(x); for (int i = 0; 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(); } } printf("%d\n", x); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...