結果
| 問題 | No.1675 Strange Minimum Query |
| ユーザー |
 ruthen
|
| 提出日時 | 2021-09-10 22:55:41 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,539 bytes |
| コンパイル時間 | 2,486 ms |
| コンパイル使用メモリ | 180,144 KB |
| 実行使用メモリ | 16,860 KB |
| 最終ジャッジ日時 | 2023-09-02 20:25:14 |
| 合計ジャッジ時間 | 13,629 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,368 KB |
| testcase_01 | AC | 2 ms
4,372 KB |
| testcase_02 | AC | 1 ms
4,368 KB |
| testcase_03 | AC | 167 ms
6,668 KB |
| testcase_04 | AC | 165 ms
9,916 KB |
| testcase_05 | AC | 56 ms
9,584 KB |
| testcase_06 | AC | 194 ms
6,820 KB |
| testcase_07 | AC | 215 ms
9,548 KB |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 280 ms
16,724 KB |
| testcase_14 | AC | 306 ms
16,784 KB |
| testcase_15 | AC | 284 ms
16,724 KB |
| testcase_16 | AC | 1 ms
4,372 KB |
| testcase_17 | AC | 52 ms
6,480 KB |
| testcase_18 | AC | 71 ms
7,108 KB |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | AC | 248 ms
15,848 KB |
| testcase_23 | AC | 173 ms
8,304 KB |
| testcase_24 | AC | 171 ms
10,988 KB |
| testcase_25 | AC | 118 ms
7,268 KB |
| testcase_26 | WA | - |
| testcase_27 | AC | 193 ms
15,140 KB |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | AC | 220 ms
9,644 KB |
| testcase_32 | AC | 315 ms
16,860 KB |
| testcase_33 | AC | 309 ms
16,724 KB |
| testcase_34 | AC | 312 ms
16,788 KB |
| testcase_35 | AC | 339 ms
16,780 KB |
| testcase_36 | AC | 337 ms
16,728 KB |
ソースコード
#include <bits/stdc++.h>
using namespace std;
// clang-format off
#include <algorithm>
#include <cassert>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
using namespace atcoder;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using vii = vector<int>;
using vll = vector<ll>;
using vdd = vector<ld>;
using vvii = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vvdd = vector<vector<ld>>;
using vvvii = vector<vector<vector<int>>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvdd = vector<vector<vector<ld>>>;
template<class T, class U> using P = pair<T, U>;
template<class T> using V1 = vector<T>;
template<class T> using V2 = vector<vector<T>>;
template<class T> using V3 = vector<vector<vector<T>>>;
template<class T> using pque = priority_queue<T, vector<T>, greater<T>>;
#define _overload3(_1, _2, _3, name, ...) name
#define rep1(n) for (ll i = 0; i < (n); i++)
#define rep2(i, n) for (ll i = 0; i < (n); i++)
#define rep3(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(...) _overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for (ll i = (n) - 1; i >= 0; i--)
#define rrep2(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rrep3(i, a, b) for (ll i = (b) - 1; i >= (a); i--)
#define rrep(...) _overload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define popcnt(x) __builtin_popcountll(x)
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end());
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr);
const int inf = 1 << 30;
const ll INF = 1ll << 60;
const ld DINF = numeric_limits<ld>::infinity();
const ll mod = 1000000007;
//const ll mod = 998244353;
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932;
const ll dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const ll dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<typename T> T min(const vector<T> &x) { return *min_element(all(x)); }
template<typename T> T max(const vector<T> &x) { return *max_element(all(x)); }
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << "(" << p.fi << ", " << p.se << ")"; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { os << "[ "; for (auto &z : v) os << z << " "; os << "]"; return os; }
#ifdef _DEBUG
#define show(x) cout << #x << " = " << x << endl;
#else
#define show(x)
#endif
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll rem(ll a, ll b) { return (a % b + b) % b; }
// clang-format on
// using mint = modint998244353;
ll modpow(ll a, ll N, ll mod) {
ll res = 1;
// 例えば3=101(2)なので、下位bitから順に1ならa倍する
while (N) {
if (N & 1) res = res * a % mod;
a = a * a % mod;
N >>= 1;
}
return res;
}
int op(int a, int b) { return min(a, b); }
int e() { return inf; }
int main() {
// IOS;
int N, Q;
cin >> N >> Q;
V1<P<int, pii>> lrB(Q);
rep(Q) {
cin >> lrB[i].se.fi >> lrB[i].se.se >> lrB[i].fi;
lrB[i].se.fi--, lrB[i].se.se--;
}
sort(all(lrB));
reverse(all(lrB));
segtree<int, op, e> Seg(N);
set<int> Set;
rep(i, N) Set.insert(i);
rep(i, Q) {
int l = lrB[i].se.fi, r = lrB[i].se.se, B = lrB[i].fi;
while (1) {
auto itr = Set.lower_bound(l);
if (itr == Set.end()) break;
if ((*itr) > r) break;
show(*itr);
show(B);
Seg.set((*itr), B);
show(Seg.get((*itr)));
Set.erase(itr);
}
int m = Seg.prod(l, r + 1);
if (m > B) {
cout << -1 << endl;
return 0;
}
}
rep(i, N) {
if (i) cout << " ";
cout << Seg.get(i);
}
cout << endl;
return 0;
}
/*
メモ
Bの大きい順にソートする
*/