Submission #1204684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204684		loom	RMQ (NOI17_rmq)	C++20	30 / 100	64 ms	24056 KiB

rmq

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

int lg2(int x){
   int p = 0;
   while((1ll<<(p+1)) <= x) p++;
   return p;
}

inline void solve(){
   int n, q;
   cin>>n>>q;
   
   vector<int> l[n], r[n];
   vector<tuple<int,int,int>> qry;
   while(q--){
      int li, ri, x;
      cin>>li>>ri>>x;

      qry.push_back({li, ri, x});
      l[li].push_back(x);
      r[ri].push_back(x);
   }

   multiset<int> st;
   int ans[n];
   for(int i=0; i<n; i++){
      for(int x : l[i]) st.insert(x);
      ans[i] = (st.empty() ? 0 : *st.rbegin());
      for(int x : r[i]) st.erase(st.find(x));
   }

   int m[n][17];
   for(int i=0; i<n; i++) m[i][0] = ans[i];

   for(int j=1; j<17; j++){
      for(int i=0; i+(1<<j)-1<n; i++){
         m[i][j] = min(m[i][j-1], m[i+(1<<(j-1))][j-1]);
      }
   }

   for(auto [li, ri, x] : qry){
      int lg = lg2(ri-li+1);

      if(x != min(m[li][lg], m[ri-(1<<lg)+1][lg])){
         for(int i=0; i<n; i++) ans[i] = -1;
         break;
      }
   }

   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: 6.9 / 23
• Subtask 2: 13.2 / 44
• Subtask 3: 9.9 / 33