#include <bits/stdc++.h> using namespace std; struct Query { int s, t, p; }; const int N = 4e5 + 3; const int S = 900; int n, q; int a[N]; Query query[N]; int block[N]; vector<int> low, up; vector<priority_queue<int>> price; vector<priority_queue<int, vector<int>, greater<int>>> tag; void build(int b) { priority_queue<int>(a + low[b], a + up[b] + 1).swap(price[b]); } void apply_update(int b) { if(tag[b].empty()) return; for(int i = low[b]; i <= up[b]; i++) { if(tag[b].top() < a[i]) { tag[b].push(a[i]); a[i] = tag[b].top(); tag[b].pop(); } } priority_queue<int, vector<int>, greater<int>>().swap(tag[b]); } int modify(int l, int r, int p) { if(block[l] == block[r]) { apply_update(block[l]); for(int i = l; i <= r; i++) if(p < a[i]) swap(a[i], p); build(block[l]); return p; } apply_update(block[l]); for(int i = l; i <= up[block[l]]; i++) if(p < a[i]) swap(a[i], p); build(block[l]); for(int i = block[l] + 1; i < block[r]; i++) { if(p < price[i].top()) { tag[i].push(p); price[i].push(p); p = price[i].top(); price[i].pop(); } } apply_update(block[r]); for(int i = low[block[r]]; i <= r; i++) if(p < a[i]) swap(a[i], p); build(block[r]); return p; } int main() { scanf("%d%d", &n, &q); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for(int i = 1; i <= q; i++) { scanf("%d%d%d", &query[i].s, &query[i].t, &query[i].p); } for(int i = 1; i <= n; i++) block[i] = (i - 1) / S + 1; low.resize(block[n] + 1); up.resize(block[n] + 1); price.resize(block[n] + 1); tag.resize(block[n] + 1); for(int i = 1; i <= block[n]; i++) { low[i] = (i - 1) * S + 1; up[i] = min(n, i * S); build(i); } for(int i = 1; i <= q; i++) { if(query[i].s <= query[i].t) cout << modify(query[i].s, query[i].t, query[i].p) << endl; else { int apply = modify(query[i].s, n, query[i].p); cout << modify(1, query[i].t, apply) << endl; } } cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << endl; return 0; }

sushi.cpp: In function 'int main()':
sushi.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
sushi.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d%d%d", &query[i].s, &query[i].t, &query[i].p);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~