Submission #922380

#TimeUsernameProblemLanguageResultExecution timeMemory
922380pccRMQ (NOI17_rmq)C++14
30 / 100
77 ms13584 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 1e5+10; vector<int> op[mxn]; int N,Q; tuple<int,int,int> req[mxn]; int arr[mxn]; int segtree[mxn*4]; void build(int now,int l,int r){ if(l == r){ segtree[now] = arr[l]; return; } int mid = (l+r)>>1; build(now*2+1,l,mid); build(now*2+2,mid+1,r); segtree[now] = min(segtree[now*2+1],segtree[now*2+2]); } int getval(int now,int l,int r,int s,int e){ if(l >=s&&e>=r)return segtree[now]; int mid = (l+r)>>1; if(mid>=e)return getval(now*2+1,l,mid,s,e); else if(mid<s)return getval(now*2+2,mid+1,r,s,e); else return min(getval(now*2+1,l,mid,s,e),getval(now*2+2,mid+1,r,s,e)); } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N>>Q; for(int i = 0;i<Q;i++){ int s,e,v; cin>>s>>e>>v; req[i] = make_tuple(s,e,v); v++; op[s].push_back(v); op[e+1].push_back(-v); } multiset<int> st; st.insert(0); for(int i = 0;i<N;i++){ for(auto &j:op[i]){ if(j>0)st.insert(j-1); else st.erase(st.find(-j-1)); } arr[i] = *st.rbegin(); } build(0,0,N-1); bool flag = true; for(int i = 0;i<Q;i++){ int s = get<0>(req[i]),e = get<1>(req[i]),v = get<2>(req[i]); if(getval(0,0,N-1,s,e) != v){ flag = false; } } if(flag)for(int i = 0;i<N;i++)cout<<arr[i]<<' '; else for(int i = 0;i<N;i++)cout<<-1<<' '; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...