Submission #1204686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204686		loom	RMQ (NOI17_rmq)	C++20	0 / 100	0 ms	328 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));
   }

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