結果
問題 |
No.2930 Larger Mex
|
ユーザー |
|
提出日時 | 2024-10-12 14:52:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 3,178 bytes |
コンパイル時間 | 1,959 ms |
コンパイル使用メモリ | 198,092 KB |
最終ジャッジ日時 | 2025-02-24 17:45:42 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; // #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> // #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); return 0; } using ll = long long; using ull = unsigned long long; using ld = long double; using vi = std::vector<int>; using vvi = std::vector<vi>; using vl = std::vector<ll>; using vii = std::vector<pair<int, int> >; using vvl = std::vector<vl>; using vll = std::vector<pair<ll , ll> >; using vd = std::vector<double>; using vvd = std::vector<vd>; using vs = std::vector<std::string>; using vvs = std::vector<vs>; using vb = std::vector<bool>; using vvb = std::vector<vb>; using vc = std::vector<char>; using vvc = std::vector<vc>; using pii = std::pair<int, int>; using pll = std::pair<ll, ll>; using piil = std::pair<pair<int, int>, ll>; using mii = std::map<int, int>; using mll = std::map<ll, ll>; using pql = std::priority_queue<ll>; using pqi = std::priority_queue<int>; using pqiil = std::priority_queue<pair<pair<int, int>, ll> >; using pqii = std::priority_queue<pair<int, int> >; #define pb push_back #define ps push #define eb emplace_back #define is insert #define er erase #define f first #define s second #define lb lower_bound #define ub upper_bound #define sf(i) sizeof(i) #define endl "\n" #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() #define rep(i, L, R) for(ll i = L;i<=R;i++) #define pcis precision template<typename T> struct infinity { static constexpr T max=std::numeric_limits<T>::max(); static constexpr T min=std::numeric_limits<T>::min(); static constexpr T value=std::numeric_limits<T>::max()/2; static constexpr T mvalue=std::numeric_limits<T>::min()/2; }; template<typename T>constexpr T INF=infinity<T>::value; constexpr ll lINF=INF<ll>; constexpr int iINF = INF<int>; constexpr ld PI = 3.1415926535897932384626; ll B[300001]; void _main() { ll N, M; cin >>N >>M; ll A[N+1]; for (ll i = 1; i<=N; i++)cin>>A[i]; priority_queue<ll, vl, greater<ll>> pq; for (ll i = 0; i<=N; i++) { pq.ps(i); } ll left = 0; ll RES = 0; ll S[N+2]; memset(S,0 ,sf(S)); for (ll i = 1; i<=N; i++) { if (left < i) { if (i != 1)B[A[i-1]] --; if (i != 1)pq.ps(A[i-1]); left = i; B[A[i]] ++; } else { B[A[i-1]] --;// 전에꺼 빼야함 pq.ps(A[i-1]); } // cout << "At " << i << " : " << "----------------" << endl; // for (ll j = 0; j<=N; j++) { // cout << B[j] << " "; // } // cout<<endl; while (left != N+1) { while (B[pq.top()]) { pq.pop(); } if (pq.top() >= M)break; left++; if (left == N+1)break; B[A[left]]++; } if (left==N+1) { break; } // for (ll j = 0; j<=N; j++) { // cout << B[j] << " "; // } // cout << endl; // i~left // cout << i << " to " << left << endl; S[left-i+1] += 1; S[N-i+2] -= 1; } for (ll i = 1; i<=N; i++) { S[i] += S[i-1]; cout << S[i] << endl; } }