제출 #284376

#제출 시각아이디문제언어결과실행 시간메모리
284376Alexa2001Sushi (JOI16_sushi)C++17
5 / 100
4141 ms262148 KiB
#include <bits/stdc++.h> using namespace std; const int Nmax = 4e5 + 5; const int B = 3; priority_queue<int, vector<int>, greater<int>> op[Nmax / B + 5]; priority_queue<int> val[Nmax / B + 5]; int n, q, m; int a[Nmax]; void init() { int i; for(i=0; i<n; ++i) val[i / B].push(a[i]); } int query1(int x, int y, int w) { y = min(y, n-1); int i, buc = x/B; for(i=buc*B; i<(buc+1)*B && i<n; ++i) { op[buc].push(a[i]); a[i] = op[buc].top(); op[buc].pop(); } while(!op[buc].empty()) op[buc].pop(); while(!val[buc].empty()) val[buc].pop(); for(i=x; i<=y; ++i) if(a[i] > w) swap(a[i], w); for(i=buc*B; i<(buc+1)*B && i < n; ++i) val[buc].push(a[i]); return w; } int query2(int buc, int x) { op[buc].push(x); val[buc].push(x); x = val[buc].top(); val[buc].pop(); return x; } int query(int x, int y, int val) { if(x > y) return query(0, y, query(x, n-1, val)); if(x/B == y/B) return query1(x, y, val); if(x%B!=0) val = query1(x, x/B*B + B - 1, val); else val = query2(x/B, val); for(int i = x/B + 1; i < y/B; ++i) val = query2(i, val); if(y%B==B-1 || y==n-1) val = query2(y/B, val); else val = query1(y/B*B, y, val); return val; } int main() { // freopen("input", "r", stdin); cin.tie(0); cin.sync_with_stdio(false); cin >> n >> q; int i; for(i=0; i<n; ++i) cin >> a[i]; m = (n-1) / B + 1; init(); while(q--) { int x, y, val; cin >> x >> y >> val; --x; --y; cout << query(x, y, val) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...