Submission #1226552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226552		lopkus	RMQ (NOI17_rmq)	C++20	0 / 100	0 ms	324 KiB

rmq

#include <bits/stdc++.h>

int main() {

  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, q;
  std::cin >> n >> q;
  std::vector<int> l(q + 1), r(q + 1), x(q + 1);
  for(int i = 1; i <= q; i++) {
    std::cin >> l[i] >> r[i] >> x[i];
    l[i] += 1;
    r[i] += 1;
    x[i] += 1;
  }
  std::vector<int> b(n + 1, 1);
  for(int i = 1; i <= q; i++) {
    for(int j = l[i]; j <= r[i]; j++) {
      b[j] = std::max(b[j], x[i]);
    }
  }
  std::vector<std::pair<int, int>> intervals[n + 1];
  for(int i = 1; i <= q; i++) {
    intervals[x[i]].push_back({l[i], r[i]});
  }
  std::vector<std::pair<int, int>> Do[n + 1];
  int can = 1;
  for(int it = 1; it <= n; it++) {
    int L = - 1, R = n + 1;
    for(auto [ll, rr] : intervals[it]) {
      L = std::max(L, ll);
      R = std::min(R, rr);
    }
    if(L > R) {
      can = 0;
      break;
    }
    Do[L].push_back({R, it});
  }
  if(!can) {
    for(int i = 1; i <= n; i++) {
      std::cout << - 1 << " ";
    }
    return 0;
  }
  std::vector<int> any(n + 1);
  std::vector<int> a(n + 1, - 1);
  for(int i = 1; i <= n; i++) {
    std::sort(Do[i].begin(), Do[i].end());
    for(auto [rr, xx] : Do[i]) {
      for(int j = i; j <= rr; j++) {
        if(!any[j] && b[j] <= xx) {
          any[j] = 1;
          a[j] = xx;
          break;
        }
      }
    }
  }
  std::vector<int> was(n + 1);
  for(int i = 1; i <= n; i++) {
    if(a[i] != - 1) {
      was[a[i]] = 1;
    }
  }
  int curr = n;
  std::vector<std::pair<int, int>> other;
  for(int i = 1; i <= n; i++) {
    if(a[i] == - 1) {
      other.push_back({b[i], i});
    }
  }
  std::sort(other.rbegin(), other.rend());
  for(int it = 0; it < other.size(); it++) {
    while(was[curr]) {
      curr--;
    }
    if(b[other[it].second] > curr) {
      can = 0;
      break;
    }
    a[other[it].second] = curr--;
  }
  if(!can) {
    for(int i = 1; i <= n; i++) {
      std::cout << - 1 << " ";
    }
    return 0;
  }
  for(int i = 1; i <= q; i++) {
    int mn = n + 1;
    for(int j = l[i]; j <= r[i]; j++) {
      mn = std::min(mn, a[j]);
    }
    if(mn != x[i]) {
      can = 0;
    }
  }
  if(!can) {
    for(int i = 1; i <= n; i++) {
      std::cout << - 1 << " ";
    }
    return 0;
  }
  for(int i = 1; i <= n; i++) {
    std::cout << --a[i] << " ";
  }
  return 0;
}

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