fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int B=500;
  4. int N,Q,A[400400],s[25050],e[25050],h[25050],ans[25050];
  5. priority_queue<int> pqMax[2*B+5], pqMin[2*B+5];
  6.  
  7. void add(int i,int &val){
  8.     int mx=pqMax[i].top();
  9.     if(mx<=val) return;
  10.     pqMax[i].pop(); pqMax[i].push(val);
  11.     pqMin[i].push(-val);
  12.     val=mx;
  13. }
  14.  
  15. void solve(int L,int R){
  16.     vector<int> cr={1,N+1};
  17.     for(int i=L;i<=R;i++) cr.push_back(s[i]), cr.push_back(e[i]+1);
  18.     sort(cr.begin(),cr.end());
  19.     cr.erase(unique(cr.begin(),cr.end()),cr.end());
  20.  
  21.     for(int i=0;i+1<cr.size();i++)
  22.         for(int j=cr[i];j<cr[i+1];j++)
  23.             pqMax[i].push(A[j]);
  24.  
  25.     for(int i=L;i<=R;i++){
  26.         int ns=lower_bound(cr.begin(),cr.end(),s[i])-cr.begin();
  27.         int ne=lower_bound(cr.begin(),cr.end(),e[i]+1)-cr.begin();
  28.         int nh=h[i];
  29.         if(ns<ne) for(int j=ns;j<ne;j++) add(j,nh);
  30.         else for(int j=ns;j+1<cr.size();j++) add(j,nh); 
  31.              for(int j=0;j<ne;j++) add(j,nh);
  32.         ans[i]=nh;
  33.     }
  34.  
  35.     for(int i=0;i+1<cr.size();i++)
  36.         for(int j=cr[i];j<cr[i+1];j++){
  37.             if(pqMin[i].empty()) break;
  38.             int mn=-pqMin[i].top();
  39.             if(mn>=A[j]) continue;
  40.             pqMin[i].pop(); pqMin[i].push(-A[j]);
  41.             A[j]=mn;
  42.         }
  43.  
  44.     for(int i=0;i<cr.size();i++) pqMax[i]=priority_queue<int>(), pqMin[i]=priority_queue<int>();
  45. }
  46.  
  47. int main(){
  48.     ios::sync_with_stdio(0); cin.tie(0);
  49.     cin >> N >> Q;
  50.     for(int i=1;i<=N;i++) cin >> A[i];
  51.     for(int i=1;i<=Q;i++) cin >> s[i] >> e[i] >> h[i];
  52.     for(int i=1;i<=Q;i+=B) solve(i,min(i+B-1,Q));
  53.     for(int i=1;i<=Q;i++) cout << ans[i] << '\n';
  54. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6 7
8
6
7
4
5
9
2 4 5
4 1 4
6 2 7
1 5 2
3 4 8
4 3 1
3 1 3
stdout
copy 
8
9
7
7
8
6
5
https://ideone.com/jjgcvF
language:
C++ (gcc 8.3)
created:
22 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!