Submission #1204912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204912		loom	RMQ (NOI17_rmq)	C++20	100 / 100	161 ms	14560 KiB

rmq

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

const int N = 1e5;
int ans[N], seg[4*N], lz[4*N], ix[4*N];
set<int> st;
int n;

void lazy(int l, int r, int p){
   seg[p] += lz[p];
   if(l != r){
      lz[p*2] += lz[p];
      lz[p*2+1] += lz[p];
   }
   lz[p] = 0;
}

void build(int l, int r, int p){
   if(l == r){
      if(l >= n) seg[p] = inf;
      ix[p] = l;
      return;
   }

   int m = (l+r)/2;
   build(l, m, p*2);
   build(m+1, r, p*2+1);

   seg[p] = min(seg[p*2], seg[p*2+1]);
   ix[p] = (seg[p*2] < seg[p*2+1] ? ix[p*2] : ix[p*2+1]);
}

void update(int l, int r, int p, int ql, int qr, int v){
   lazy(l, r, p);

   if(qr < l or r < ql) return;
   if(ql <= l and r <= qr){
      lz[p] += v;
      lazy(l, r, p);
      return;
   }

   int m = (l+r)/2;
   update(l, m, p*2, ql, qr, v);
   update(m+1, r, p*2+1, ql, qr, v);

   seg[p] = min(seg[p*2], seg[p*2+1]);
   ix[p] = (seg[p*2] < seg[p*2+1] ? ix[p*2] : ix[p*2+1]);
}

pair<int,int> query(int l, int r, int p, int ql, int qr){
   lazy(l, r, p);

   if(qr < l or r < ql) return {inf, -1};
   if(ql <= l and r <= qr) return {seg[p], ix[p]};

   int m = (l+r)/2;
   auto [mn1, ix1] = query(l, m, p*2, ql, qr);
   auto [mn2, ix2] = query(m+1, r, p*2+1, ql, qr);

   return {min(mn1, mn2), (mn1 < mn2 ? ix1 : ix2)};
}

void upd(int ql, int qr, int v){
   update(0, N-1, 1, ql, qr, v);
}

pair<int,int> qry(int ql, int qr){
   return query(0, N-1, 1, ql, qr);
}

void impos(){
   for(int i=0; i<n; i++) cout<<"-1 ";
   exit(0);
}

void add(){
   auto [mn, ix] = qry(0, n-1);
   while(mn == 0){
      st.insert(ix);
      upd(ix, ix, inf);

      auto [mn2, ix2] = qry(0, n-1);
      mn = mn2;
      ix = ix2;
   }
}

inline void solve(){
   int q;
   cin>>n>>q;
   build(0, N-1, 1);
   
   vector<pair<int,int>> v[n];
   while(q--){
      int l, r, x;
      cin>>l>>r>>x;
      v[x].push_back({l, r});
      upd(l, r, 1);
   }

   add();
   for(int i=0; i<n; i++){
      if(v[i].empty()){
         if(st.empty()) impos();
         auto it = st.begin();
         ans[*it] = i;
         st.erase(it);
         continue;
      }

      int ml = 0, mr = inf;
      for(auto [l, r] : v[i]){
         upd(l, r, -1);
         ml = max(ml, l);
         mr = min(mr, r);
      }
      add();

      auto it = st.lower_bound(ml);
      if(it == st.end() or *it > mr) impos();
      ans[*it] = i;
      st.erase(it);
   }

   for(int i=0; i<n; i++) cout<<ans[i]<<" ";
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33