Submission #218193

#	Time	Username	Problem	Language	Result	Execution time	Memory
218193		quocnguyen1012	RMQ (NOI17_rmq)	C++14	100 / 100	67 ms	10104 KiB

rmq

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

vector<ii> vec[maxn];
int N, a[maxn], used[maxn], last, Q;
set<int> se;

void no_sol(void)
{
  for(int i = 1; i <= N; ++i)
    cout << -1 << ' ';
  exit(0);
}

void add(int val, int l, int r, int L, int R)
{
  auto it = se.lower_bound(l);
  bool add = false;
  while(it != se.end() && *it <= r){
    if(L <= *it && *it <= R && !add){
      used[val] = 1;
      a[*it] = val;
      add = 1;
    }
    else{
      while(last >= 1 && used[last]) --last;
      if(last <= val){
        no_sol();
      }
      used[last] = 1;
      a[*it] = last;
    }
    ++it;
    se.erase(prev(it));
  }
  if(!add) no_sol();
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL

  cin >> N >> Q; last = N;
  while(Q--){
    int l, r, v; cin >> l >> r >> v;
    ++l; ++r; ++v;
    vec[v].eb(l, r);
  }
  for(int i = 1; i <= N; ++i)
    se.insert(i);
  for(int i = N; i >= 1; --i) if(vec[i].size()){
    used[i] = true;
    int lmax = 0, rmin = N, lmin = N, rmax = 0;
    for(auto & it : vec[i]){
      lmax = max(lmax, it.fi);
      rmin = min(rmin, it.se);
      lmin = min(lmin, it.fi);
      rmax = max(rmax, it.se);
    }
    if(lmax > rmin){
      no_sol();
    }
    add(i, lmin, rmax, lmax, rmin);
  }
  for(auto it : se){
    while(last >= 1 && used[last]) --last;
    if(last < 1) no_sol();
    a[it] = last;
    used[last] = 1;
  }
  for(int i = 1; i <= N; ++i)
    cout << a[i] - 1 << ' ';
}

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