結果
問題 | No.2930 Larger Mex |
ユーザー |
![]() |
提出日時 | 2024-10-12 18:10:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,747 bytes |
コンパイル時間 | 6,354 ms |
コンパイル使用メモリ | 323,212 KB |
実行使用メモリ | 16,896 KB |
最終ジャッジ日時 | 2024-10-12 18:10:25 |
合計ジャッジ時間 | 14,423 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 50 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>namespace neguse {}using namespace std;using namespace atcoder;using namespace neguse;typedef long long ll;typedef long double ld;typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef vector<int> vi;typedef vector<ll> vll;typedef vector<ld> vld;typedef vector<vi> vvi;typedef vector<vll> vvll;typedef vector<string> vs;typedef vector<pii> vpii;typedef vector<pll> vpll;#define _overload3(_1, _2, _3, name, ...) name#define _rep(i, n) repi(i, 0, n)#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)#define _rrep(i, n) rrepi(i, n - 1, -1)#define rrepi(i, a, b) for (int i = int(a); i > int(b); --i)#define rrep(...) _overload3(__VA_ARGS__, rrepi, _rrep)(__VA_ARGS__)#define _each1(i, v) for (auto &i : v)#define _each2(i, j, v) for (auto &[i, j] : v)#define each(...) _overload3(__VA_ARGS__, _each2, _each1, )(__VA_ARGS__)#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()#define SUM(x) accumulate(all(x), 0LL)#define MAX(x) *max_element(all(x))#define MIN(x) *min_element(all(x))#define ACC(x, acc) partial_sum(all(x), acc.begin()+1)#define SORT(x) sort(all(x))#define RSORT(x) sort(rall(x))#define REVERSE(x) reverse(all(x))#define dump(x) cerr << #x << " = " << (x) << '\n'#define print(x) cout << (x) << '\n'#define yes(f) cout << ((f) ? "Yes" : "No") << '\n'#define ge(v, x) (int)(lower_bound(all(v), x) - v.begin())#define gt(v, x) (int)(upper_bound(all(v), x) - v.begin())#define le(v, x) (int)(upper_bound(all(v), x) - v.begin()) - 1#define lt(v, x) (int)(lower_bound(all(v), x) - v.begin()) - 1template <class T> bool chmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }template <class T> bool chmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); }istream &operator>>(istream &is, modint998244353 &a) { int64_t t; is >> t; a = t; return is; }istream &operator>>(istream &is, modint1000000007 &a) { int64_t t; is >> t; a = t; return is; }template <class S, class T> ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '(' << p.first << ", " << p.second << ')'; }template <class S, class T> istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; }template <class T> istream &operator>>(istream &is, vector<T> &v) { for (T &x : v) is >> x; return is; }template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &x : v) os << x << ' '; return os; }template <class T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { for (const vector<T> &x : v) os << x << '\n'; return os; }#include <set>#include <cassert>#include <iostream>namespace neguse {template<typename T>class range_set {public:range_set() {S.insert({-inf, -inf});S.insert({inf, inf});}std::set<std::pair<T, T>> &get_all() { return S; }void insert(T l, T r) {auto itl = std::prev(S.upper_bound({l, inf}));auto itr = std::prev(S.upper_bound({r, inf}));if (itl->first <= l && l <= itl->second) l = itl->first;else itl++;if (itr->first <= r && r <= itr->second) r = itr->second;itr++;while (itl != itr) {cnt -= itl->second - itl->first;itl = S.erase(itl);}S.insert({l, r});cnt += r - l;}void insert(T x) { insert(x, x+1); }void erase(T l, T r) {auto itl = std::prev(S.upper_bound({l, inf}));auto itr = std::prev(S.upper_bound({r, inf}));if (itl->first <= l && l < itl->second) {if (l != itl->first) {S.insert({itl->first, l});cnt += l - itl->first;}} else itl++;if (itr->first < r && r < itr->second) {S.insert({r, itr->second});cnt += itr->second - r;}if (r != itr->first) itr++;while (itl != itr) {cnt -= itl->second - itl->first;itl = S.erase(itl);}}void erase(T x) { erase(x, x+1); }bool contains(T l, T r) {auto it = std::prev(S.upper_bound({l, inf}));return it->first <= l && r <= it->second;}bool contains(T x) { return contains(x, x+1); }T count() { return cnt; }T size() { return S.size() - 2; }std::pair<T, T> get(T x) {auto it = S.upper_bound({x, inf});it--;if (it->first <= x && x < it->second) return *it;return {-inf, -inf};}range_set<T> intersect(T l, T r) {range_set<T> res;auto itl = std::prev(S.upper_bound({l, inf}));auto itr = std::prev(S.upper_bound({r, inf}));if (l < itl->second) res.insert(std::max(l, itl->first), std::min(r, itl->second));while (itl++ != itr) res.insert(std::max(l, itl->first), std::min(r, itl->second));if (itr->first < r) res.insert(std::max(l, itr->first), std::min(r, itr->second));return res;}T mex(T x = 0) {auto [l, r] = get(x);if (l <= x && x < r) return r;return x;}void debug() {for (auto [l, r] : S) {if (l == inf || l == -inf) continue;std::cout << "[" << l << ", " << r << ")" << " ";}std::cout << '\n';}private:std::set<std::pair<T, T>> S;T cnt = 0, inf = std::numeric_limits<T>::max() / 2;};}int main() {int N, M;cin >> N >> M;vi A(N);cin >> A;if (M == 0) {rep(i, N) cout << N+1-A[i] << " \n"[i==N-1];return 0;}range_set<int> rs;map<int, int> mp;deque<pii> dq;vector<ll> ans(N+2);rep(r, N) {dq.emplace_back(r, A[r]);if (mp[A[r]]++ == 0) rs.insert(A[r]);while (rs.mex() >= M) {auto [l, x] = dq.front(); dq.pop_front();if (--mp[x] == 0) rs.erase(x);}if (!dq.empty()) {int l = dq.front().first;ans[1]++;ans[r-l+2]--;}}rep(i, N+1) ans[i+1] += ans[i];rep(i, 1, N+1) ans[i] = N+1-i-ans[i];rep(i, 1, N+1) cout << ans[i] << " \n"[i==N];return 0;}