Submission #426721

#TimeUsernameProblemLanguageResultExecution timeMemory
426721nots0fastRMQ (NOI17_rmq)C++17
0 / 100
2 ms204 KiB
#include <bits/stdc++.h> using namespace std; #define mp(a,b) make_pair(a,b) #define ff first #define setp(a) setprecision(a)<<fixed #define ss second #define fori(v) for(ll i=0; i<v; i++) #define forj(v) for(ll j=0; j<v; j++) #define fork(v) for(ll k=0; k<v; k++) #define forl(v) for(ll l=0; l<v; l++) #define fort(v) for(ll t=0; t<v; t++) #define forz(v) for(ll z=0; z<v; z++) #define forx(v) for(ll x=0; x<v; x++) #define fory(v) for(ll y=0; y<v; y++) #define ll long long #define ld long double #define MAX (int)(pow(10,6) + 10) #define pb(a) push_back(a) const ll INF = 0x3f3f3f3f; const ll inf = pow(10,18); ll modulo = pow(10,9) + 7; void badcase(ll n){ fori(n){ cout<<-1<<' '; } } void deal(){ ll n, m; cin>>n>>m; vector<vector<pair<ll, ll> > > arr(n); fori(m){ ll li, ri, v; cin>>li>>ri>>v; arr[v].pb(mp(li, ri)); } vector<vector<ll> > que; vector<ll> ans(n, -1); fori(n){ if((ll)arr[i].size() == 0){ continue; } ll l = -1, r = n+1; for(auto& el : arr[i]){ l = max(l, el.ff); r = min(r, el.ss); } if(l > r){ badcase(n); return; } que.pb(vector<ll>({l, r, i})); } sort(que.begin(), que.end()); set<ll> free; fori(n){ free.insert(i); } for(auto& el : que){ ll li = el[0], ri = el[1]; auto it = free.lower_bound(li); if(it == free.end() || (*it) > ri){ badcase(n); return; } ans[*it] = el[2]; free.erase(it); } vector<vector<ll> > toadd(n); for(ll i = n-1; i>-1; i--){ if((ll)arr[i].size() == 0){ continue; } for(auto& el : arr[i]){ ll li = el.ff, ri = el.ss; auto it = free.lower_bound(li); while(it!=free.end() && (*it) <= ri){ auto itn = it; ++itn; toadd[i].pb(*it); free.erase(*it); it = itn; } } } fori(n){ for(auto& el : toadd[i]){ free.insert(el); } if((ll)arr[i].size() != 0){ continue; } if((ll)free.size() == 0){ badcase(n); return; } auto it = free.begin(); ans[*it] = i; free.erase(it); } fori(n){ cout<<ans[i]<<' '; } } int main(){ cin.tie(0); ios_base::sync_with_stdio(0); deal(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...