結果
| 問題 | No.3465 Lis! Lis! Lis! |
| コンテスト | |
| ユーザー |
 だれ
|
| 提出日時 | 2026-02-28 15:47:58 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 24,133 bytes |
| 記録 | |
| コンパイル時間 | 6,612 ms |
| コンパイル使用メモリ | 356,272 KB |
| 実行使用メモリ | 43,536 KB |
| 最終ジャッジ日時 | 2026-02-28 15:49:00 |
| 合計ジャッジ時間 | 60,382 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 WA * 20 TLE * 1 |
ソースコード
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_set>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
namespace atcoder {
ostream& operator<<(ostream& os, modint x) { return os << x.val(); }
template <int N>
ostream& operator<<(ostream& os, static_modint<N> x) {
return os << x.val();
}
istream& operator>>(istream& is, modint x) {
long long a;
is >> a;
x = a;
return is;
}
template <int N>
istream& operator>>(istream& is, static_modint<N> x) {
long long a;
is >> a;
x = a;
return is;
}
} // namespace atcoder
#endif
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define UNIQUE(x) \
std::sort((x).begin(), (x).end()); \
(x).erase(std::unique((x).begin(), (x).end()), (x).end())
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using i32 = int;
using ld = long double;
using f64 = double;
template <class T, class U>
bool chmin(T& a, const U& b) {
return (b < a) ? (a = b, true) : false;
}
template <class T, class U>
bool chmax(T& a, const U& b) {
return (b > a) ? (a = b, true) : false;
}
template <class T = std::string, class U = std::string>
inline void YesNo(bool f = 0, const T yes = "Yes", const U no = "No") {
if (f)
std::cout << yes << "\n";
else
std::cout << no << "\n";
}
namespace io {
template <class T, class U>
istream& operator>>(istream& i, pair<T, U>& p) {
i >> p.first >> p.second;
return i;
}
template <class T, class U>
ostream& operator<<(ostream& o, pair<T, U>& p) {
o << p.first << " " << p.second;
return o;
}
template <typename T>
istream& operator>>(istream& i, vector<T>& v) {
rep(j, v.size()) i >> v[j];
return i;
}
template <typename T>
string join(vector<T>& v) {
stringstream s;
rep(i, v.size()) s << ' ' << v[i];
return s.str().substr(1);
}
template <typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
if (v.size()) o << join(v);
return o;
}
template <typename T>
string join(vector<vector<T>>& vv) {
string s = "\n";
rep(i, vv.size()) s += join(vv[i]) + "\n";
return s;
}
template <typename T>
ostream& operator<<(ostream& o, vector<vector<T>>& vv) {
if (vv.size()) o << join(vv);
return o;
}
void OUT() { std::cout << "\n"; }
template <class Head, class... Tail>
void OUT(Head&& head, Tail&&... tail) {
std::cout << head;
if (sizeof...(tail)) std::cout << ' ';
OUT(std::forward<Tail>(tail)...);
}
void OUTL() { std::cout << std::endl; }
template <class Head, class... Tail>
void OUTL(Head&& head, Tail&&... tail) {
std::cout << head;
if (sizeof...(tail)) std::cout << ' ';
OUTL(std::forward<Tail>(tail)...);
}
void IN() {}
template <class Head, class... Tail>
void IN(Head&& head, Tail&&... tail) {
cin >> head;
IN(std::forward<Tail>(tail)...);
}
} // namespace io
using namespace io;
namespace useful {
long long modpow(long long a, long long b, long long mod) {
long long res = 1;
while (b) {
if (b & 1) res *= a, res %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return res;
}
bool is_pow2(long long x) { return x > 0 && (x & (x - 1)) == 0; }
template <class T>
void rearrange(vector<T>& a, vector<int>& p) {
vector<T> b = a;
for (int i = 0; i < int(a.size()); i++) {
a[i] = b[p[i]];
}
return;
}
template <std::forward_iterator I>
std::vector<std::pair<typename std::iterator_traits<I>::value_type, int>>
run_length_encoding(I s, I t) {
if (s == t) return {};
std::vector<std::pair<typename std::iterator_traits<I>::value_type, int>>
res;
res.emplace_back(*s, 1);
for (auto it = ++s; it != t; it++) {
if (*it == res.back().first)
res.back().second++;
else
res.emplace_back(*it, 1);
}
return res;
}
vector<int> linear_sieve(int n) {
vector<int> primes;
vector<int> res(n + 1);
iota(all(res), 0);
for (int i = 2; i <= n; i++) {
if (res[i] == i) primes.emplace_back(i);
for (auto j : primes) {
if (j * i > n) break;
res[j * i] = j;
}
}
return res;
// return primes;
}
template <class T>
vector<long long> dijkstra(vector<vector<pair<int, T>>>& graph, int start) {
int n = graph.size();
vector<long long> res(n, 2e18);
res[start] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>,
greater<pair<long long, int>>>
que;
que.push({0, start});
while (!que.empty()) {
auto [c, v] = que.top();
que.pop();
if (res[v] < c) continue;
for (auto [nxt, cost] : graph[v]) {
auto x = c + cost;
if (x < res[nxt]) {
res[nxt] = x;
que.push({x, nxt});
}
}
}
return res;
}
} // namespace useful
using namespace useful;
template <class T, T l, T r>
struct RandomIntGenerator {
std::random_device seed;
std::mt19937_64 engine;
std::uniform_int_distribution<T> uid;
RandomIntGenerator() {
engine = std::mt19937_64(seed());
uid = std::uniform_int_distribution<T>(l, r);
}
T gen() { return uid(engine); }
};
// http://judge.yosupo.jp/submission/247593
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_lis_query"
#include <algorithm>
#include <utility>
#include <vector>
namespace nachia {
int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
return __builtin_popcountll(c);
#else
c = (c & (~0ull / 3)) + ((c >> 1) & (~0ull / 3));
c = (c & (~0ull / 5)) + ((c >> 2) & (~0ull / 5));
c = (c & (~0ull / 17)) + ((c >> 4) & (~0ull / 17));
c = (c * (~0ull / 257)) >> 56;
return c;
#endif
}
// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return 63 - __builtin_clzll(x);
#else
using u64 = unsigned long long;
int q = (x >> 32) ? 32 : 0;
auto m = x >> q;
constexpr u64 hi = 0x8888'8888;
constexpr u64 mi = 0x1111'1111;
m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31;
q += (m & 0xf) << 2;
q += 0x3333'3333'2222'1100 >> (((x >> q) & 0xf) << 2) & 0xf;
return q;
#endif
}
// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return __builtin_ctzll(x);
#else
return MsbIndex(x & -x);
#endif
}
} // namespace nachia
namespace nachia {
struct WaveletMatrix {
using u64 = unsigned long long;
struct WordBlock {
u64 table;
int ptr;
};
int n;
int S;
int logS;
std::vector<std::vector<WordBlock>> Table;
WaveletMatrix() {}
WaveletMatrix(int maxVal, std::vector<int> A) {
S = 1;
logS = 0;
n = A.size();
while (S <= maxVal) {
S *= 2;
logS += 1;
}
Table.resize(logS);
for (int d = logS - 1; d >= 0; d--) {
std::vector<WordBlock> tableBuf(n / 64 + 2, {0, 0});
for (int i = 0; i < n; i++)
tableBuf[i / 64].table |= (u64)((A[i] >> d) & 1) << (i % 64);
for (int i = 1; i <= n / 64 + 1; i++)
tableBuf[i].ptr =
tableBuf[i - 1].ptr + Popcount(tableBuf[i - 1].table);
std::vector<int> buf;
for (int b : {0, 1 << d})
for (int a : A)
if ((a & (1 << d)) == b) buf.push_back(a);
std::swap(Table[d], tableBuf);
std::swap(A, buf);
}
}
int getLevelRank(int level, int p) const {
int res = Table[level][p / 64].ptr +
Popcount(Table[level][p / 64].table & ~(~(u64)0 << (p % 64)));
return res;
}
int getLeftPointer(int level, int p) const {
return p - getLevelRank(level, p);
}
int getRightPointer(int level, int p) const {
return n - Table[level].back().ptr + getLevelRank(level, p);
}
int get(int p) const {
int res = 0;
for (int d = logS - 1; d >= 0; d--) {
res *= 2;
if (Table[d][p / 64].table & ((u64)1 << (p % 64))) {
res |= 1;
p = getRightPointer(d, p);
} else {
p = getLeftPointer(d, p);
}
}
return res;
}
int count(int l, int r, int val) const {
for (int d = logS - 1; d >= 0; d--) {
if (val & (1 << d)) {
l = getRightPointer(d, l);
r = getRightPointer(d, r);
} else {
l = getLeftPointer(d, l);
r = getLeftPointer(d, r);
}
}
return r - l;
}
int countRange(int l, int r, int rval) const {
if (rval == 0) return 0;
int ans = 0;
for (int d = logS - 1; d >= 0; d--) {
if (rval & (1 << d)) {
ans += getLeftPointer(d, r) - getLeftPointer(d, l);
l = getRightPointer(d, l);
r = getRightPointer(d, r);
} else {
l = getLeftPointer(d, l);
r = getLeftPointer(d, r);
}
}
return ans;
}
int count(int l, int r, int lval, int rval) const {
return countRange(l, r, rval) - countRange(l, r, lval);
}
int getKthSmallest(int l, int r, int k) const {
int res = 0;
for (int d = logS - 1; d >= 0; d--) {
res *= 2;
int zerocnt = r - l;
zerocnt -= getLevelRank(d, r);
zerocnt += getLevelRank(d, l);
if (k < zerocnt) {
l = getLeftPointer(d, l);
r = getLeftPointer(d, r);
} else {
res += 1;
k -= zerocnt;
l = getRightPointer(d, l);
r = getRightPointer(d, r);
}
}
return res;
}
};
} // namespace nachia
namespace nachia {
struct RangeLis {
private:
int n;
WaveletMatrix ds;
using VectorIter = std::vector<int>::iterator;
struct Split {
std::vector<int> I;
std::vector<int> valL;
std::vector<int> valR;
};
static Split SplitIndex(VectorIter A, int n, int m) {
Split res;
res.I.resize(n);
res.valL.resize(m);
res.valR.resize(n - m);
for (int i = 0; i < m; i++) res.I[A[i]] += 1;
for (int i = 0; i < n - 1; i++) res.I[i + 1] += res.I[i];
for (int i = 0; i < m; i++) {
int a = A[i];
A[i] = res.I[a] - 1;
res.valL[A[i]] = a;
}
for (int i = m; i < n; i++) {
int a = A[i];
A[i] = a - res.I[a];
res.valR[A[i]] = a;
}
return res;
}
static std::vector<int> CertainOperator(int n, VectorIter a, VectorIter b) {
if (n == 1) return {0};
int m = n / 2;
auto [AI, AvalL, AvalR] = SplitIndex(a, n, m);
auto [BI, BvalL, BvalR] = SplitIndex(b, n, m);
auto resL = CertainOperator(m, a, b);
auto resR = CertainOperator(n - m, a + m, b + m);
std::vector<int> depV(n);
std::vector<int> depH(n);
for (int i = 0; i < m; i++) {
depH[AvalL[i]] = BvalL[resL[i]];
depV[BvalL[resL[i]]] = AvalL[i];
}
for (int i = 0; i < n - m; i++) {
depH[AvalR[i]] = BvalR[resR[i]] - (n + 1) + 1;
depV[BvalR[resR[i]]] = AvalR[i] - (n + 1) + 1;
}
std::vector<int> res(n, -1);
int xi = n;
for (int yi = 0; yi <= n; yi++) {
while (0 < xi) {
if (depV[xi - 1] <= yi - (n + 1) || yi <= depV[xi - 1]) break;
xi--;
if (0 <= depV[xi] && depV[xi] <= yi) {
res[depV[xi]] = xi;
}
}
if (yi != n) {
if (depH[yi] <= xi - (n + 1) || xi <= depH[yi]) {
xi--;
res[yi] = xi;
} else {
if (depH[yi] < 0 && xi - (n + 1) <= depH[yi]) {
res[yi] = depH[yi] + (n + 1) - 1;
}
}
}
}
return res;
}
public:
static std::vector<int> MakeTableIn(VectorIter A, int n) {
if (n == 1) return {0, 1};
int m = n / 2;
auto [I, valL, valR] = SplitIndex(A, n, m);
std::vector<int> res(n * 2, -1);
std::vector<int> mapL(n);
std::vector<int> opL(n);
{
auto BL = MakeTableIn(A, m);
int j = 0;
int k = 0;
for (int i = 0; i < m * 2; i++) {
int src = i < m ? n - m + i : n + valL[i - m];
while (k < n - m && valR[k] < src - n) {
mapL[j] = n + valR[k];
opL[j++] = valR[k++];
}
if (BL[i] < m) {
mapL[j] = src;
opL[j++] = valL[BL[i]];
} else {
res[src] = (n - m) * 2 + BL[i];
}
}
while (k < n - m) {
mapL[j] = n + valR[k];
opL[j++] = valR[k++];
}
}
std::vector<int> mapR(n);
std::vector<int> opR(n);
{
auto BR = MakeTableIn(A + m, n - m);
std::vector<int> mapinv(n + n - m, 1);
for (int i = 0; i < n - m; i++) {
int dest = (BR[i] < n - m) ? valR[BR[i]] : (m + BR[i]);
res[i] = dest;
mapinv[dest] = 0;
}
mapinv[0] -= 1;
for (int i = 1; i < n + n - m; i++) mapinv[i] += mapinv[i - 1];
for (int i = n - m; i < (n - m) * 2; i++) {
int dest = (BR[i] < n - m) ? valR[BR[i]] : (m + BR[i]);
opR[valR[i - (n - m)]] = mapinv[dest];
mapR[mapinv[dest]] = dest;
}
for (int i = 0; i < m; i++) {
int dest = mapinv[valL[i]];
opR[valL[i]] = dest;
mapR[dest] = valL[i];
}
}
std::vector<int> opLInv(n);
for (int i = 0; i < n; i++) opLInv[opL[i]] = i;
auto mid = CertainOperator(n, opLInv.begin(), opR.begin());
for (int i = 0; i < n; i++) res[mapL[i]] = mapR[mid[i]];
return res;
}
static std::vector<int> MakeTable(std::vector<int> A) {
int n = A.size();
auto B = MakeTableIn(A.begin(), n);
std::vector<int> res(n);
for (int i = 0; i < n * 2; i++)
if (B[i] < n) res[B[i]] = std::max(0, i - n + 1);
return res;
}
template <class Elem>
static std::vector<int> InterpretAsPermutation(
const std::vector<Elem>& seq) {
int n = int(seq.size());
std::vector<int> I(n);
for (int i = 0; i < n; i++) I[i] = n - 1 - i;
std::stable_sort(I.begin(), I.end(),
[&](int l, int r) { return seq[l] < seq[r]; });
return I;
}
RangeLis() : n(0) {}
template <class Elem>
RangeLis(const std::vector<Elem>& seq)
: n(int(seq.size())), ds(n, MakeTable(InterpretAsPermutation(seq))) {}
int lis(int l, int r) {
if (l == r) return 0;
return ds.countRange(l, r, l + 1);
}
};
} // namespace nachia
#include <cctype>
#include <cstdint>
#include <cstdio>
#include <string>
namespace nachia {
struct CInStream {
private:
static const unsigned int INPUT_BUF_SIZE = 1 << 17;
unsigned int p = INPUT_BUF_SIZE;
static char Q[INPUT_BUF_SIZE];
public:
using MyType = CInStream;
char seekChar() {
if (p == INPUT_BUF_SIZE) {
size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin);
if (len != INPUT_BUF_SIZE) Q[len] = '\0';
p = 0;
}
return Q[p];
}
void skipSpace() {
while (isspace(seekChar())) p++;
}
private:
template <class T, int sp = 1>
T nextUInt() {
if constexpr (sp) skipSpace();
T buf = 0;
while (true) {
char tmp = seekChar();
if ('9' < tmp || tmp < '0') break;
buf = buf * 10 + (tmp - '0');
p++;
}
return buf;
}
public:
uint32_t nextU32() { return nextUInt<uint32_t>(); }
int32_t nextI32() {
skipSpace();
if (seekChar() == '-') {
p++;
return (int32_t)(-nextUInt<uint32_t, 0>());
}
return (int32_t)nextUInt<uint32_t, 0>();
}
uint64_t nextU64() { return nextUInt<uint64_t>(); }
int64_t nextI64() {
skipSpace();
if (seekChar() == '-') {
p++;
return (int64_t)(-nextUInt<int64_t, 0>());
}
return (int64_t)nextUInt<int64_t, 0>();
}
template <class T>
T nextInt() {
skipSpace();
if (seekChar() == '-') {
p++;
return -nextUInt<T, 0>();
}
return nextUInt<T, 0>();
}
char nextChar() {
skipSpace();
char buf = seekChar();
p++;
return buf;
}
std::string nextToken() {
skipSpace();
std::string buf;
while (true) {
char ch = seekChar();
if (isspace(ch) || ch == '\0') break;
buf.push_back(ch);
p++;
}
return buf;
}
MyType& operator>>(unsigned int& dest) {
dest = nextU32();
return *this;
}
MyType& operator>>(int& dest) {
dest = nextI32();
return *this;
}
MyType& operator>>(unsigned long& dest) {
dest = nextU64();
return *this;
}
MyType& operator>>(long& dest) {
dest = nextI64();
return *this;
}
MyType& operator>>(unsigned long long& dest) {
dest = nextU64();
return *this;
}
MyType& operator>>(long long& dest) {
dest = nextI64();
return *this;
}
MyType& operator>>(std::string& dest) {
dest = nextToken();
return *this;
}
MyType& operator>>(char& dest) {
dest = nextChar();
return *this;
}
} cin;
struct FastOutputTable {
char LZ[1000][4] = {};
char NLZ[1000][4] = {};
constexpr FastOutputTable() {
using u32 = uint_fast32_t;
for (u32 d = 0; d < 1000; d++) {
LZ[d][0] = ('0' + d / 100 % 10);
LZ[d][1] = ('0' + d / 10 % 10);
LZ[d][2] = ('0' + d / 1 % 10);
LZ[d][3] = '\0';
}
for (u32 d = 0; d < 1000; d++) {
u32 i = 0;
if (d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10);
if (d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10);
if (d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10);
NLZ[d][i++] = '\0';
}
}
};
struct COutStream {
private:
using u32 = uint32_t;
using u64 = uint64_t;
using MyType = COutStream;
static const u32 OUTPUT_BUF_SIZE = 1 << 17;
static char Q[OUTPUT_BUF_SIZE];
static constexpr FastOutputTable TB = FastOutputTable();
u32 p = 0;
static constexpr u32 P10(u32 d) { return d ? P10(d - 1) * 10 : 1; }
static constexpr u64 P10L(u32 d) { return d ? P10L(d - 1) * 10 : 1; }
template <class T, class U>
static void Fil(T& m, U& l, U x) {
m = l / x;
l -= m * x;
}
public:
void next_dig9(u32 x) {
u32 y;
Fil(y, x, P10(6));
nextCstr(TB.LZ[y]);
Fil(y, x, P10(3));
nextCstr(TB.LZ[y]);
nextCstr(TB.LZ[x]);
}
void nextChar(char c) {
Q[p++] = c;
if (p == OUTPUT_BUF_SIZE) {
fwrite(Q, p, 1, stdout);
p = 0;
}
}
void nextEoln() { nextChar('\n'); }
void nextCstr(const char* s) {
while (*s) nextChar(*(s++));
}
void nextU32(uint32_t x) {
u32 y = 0;
if (x >= P10(9)) {
Fil(y, x, P10(9));
nextCstr(TB.NLZ[y]);
next_dig9(x);
} else if (x >= P10(6)) {
Fil(y, x, P10(6));
nextCstr(TB.NLZ[y]);
Fil(y, x, P10(3));
nextCstr(TB.LZ[y]);
nextCstr(TB.LZ[x]);
} else if (x >= P10(3)) {
Fil(y, x, P10(3));
nextCstr(TB.NLZ[y]);
nextCstr(TB.LZ[x]);
} else if (x >= 1)
nextCstr(TB.NLZ[x]);
else
nextChar('0');
}
void nextI32(int32_t x) {
if (x >= 0)
nextU32(x);
else {
nextChar('-');
nextU32((u32)-x);
}
}
void nextU64(uint64_t x) {
u32 y = 0;
if (x >= P10L(18)) {
Fil(y, x, P10L(18));
nextU32(y);
Fil(y, x, P10L(9));
next_dig9(y);
next_dig9(x);
} else if (x >= P10L(9)) {
Fil(y, x, P10L(9));
nextU32(y);
next_dig9(x);
} else
nextU32(x);
}
void nextI64(int64_t x) {
if (x >= 0)
nextU64(x);
else {
nextChar('-');
nextU64((u64)-x);
}
}
template <class T>
void nextInt(T x) {
if (x < 0) {
nextChar('-');
x = -x;
}
if (!(0 < x)) {
nextChar('0');
return;
}
std::string buf;
while (0 < x) {
buf.push_back('0' + (int)(x % 10));
x /= 10;
}
for (int i = (int)buf.size() - 1; i >= 0; i--) {
nextChar(buf[i]);
}
}
void writeToFile(bool flush = false) {
fwrite(Q, p, 1, stdout);
if (flush) fflush(stdout);
p = 0;
}
COutStream() { Q[0] = 0; }
~COutStream() { writeToFile(); }
MyType& operator<<(unsigned int tg) {
nextU32(tg);
return *this;
}
MyType& operator<<(unsigned long tg) {
nextU64(tg);
return *this;
}
MyType& operator<<(unsigned long long tg) {
nextU64(tg);
return *this;
}
MyType& operator<<(int tg) {
nextI32(tg);
return *this;
}
MyType& operator<<(long tg) {
nextI64(tg);
return *this;
}
MyType& operator<<(long long tg) {
nextI64(tg);
return *this;
}
MyType& operator<<(const std::string& tg) {
nextCstr(tg.c_str());
return *this;
}
MyType& operator<<(const char* tg) {
nextCstr(tg);
return *this;
}
MyType& operator<<(char tg) {
nextChar(tg);
return *this;
}
} cout;
char CInStream::Q[INPUT_BUF_SIZE];
char COutStream::Q[OUTPUT_BUF_SIZE];
} // namespace nachia
int main() {
std::cout << fixed << setprecision(15);
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n, m;
IN(n, m);
vector<vector<pair<int, i64>>> g(n + 1);
vector<array<int, 3>> Q(m);
rep(i, m) {
int l, r, k;
IN(l, r, k);
l--;
Q[i] = {l, r, k};
if (k > r - l) {
OUT("No");
return 0;
}
g[r].emplace_back(l, k);
}
rep(i, n) {
g[i + 1].emplace_back(i, 1);
g[i].emplace_back(i + 1, 0);
}
auto z = dijkstra(g, n);
z.pop_back();
for (auto& e : z) e = n + 1 - e;
auto ds = nachia::RangeLis(z);
for (auto [l, r, k] : Q) {
if (ds.lis(l, r) != k) {
OUT("No");
return 0;
}
}
OUT("Yes");
OUT(z);
}