結果
問題 | No.1675 Strange Minimum Query |
ユーザー | hamath |
提出日時 | 2021-09-10 21:50:19 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 276 ms / 2,000 ms |
コード長 | 9,038 bytes |
コンパイル時間 | 3,782 ms |
コンパイル使用メモリ | 235,900 KB |
実行使用メモリ | 20,408 KB |
最終ジャッジ日時 | 2024-06-11 23:29:12 |
合計ジャッジ時間 | 13,241 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 166 ms
12,016 KB |
testcase_04 | AC | 155 ms
13,532 KB |
testcase_05 | AC | 16 ms
7,552 KB |
testcase_06 | AC | 196 ms
13,412 KB |
testcase_07 | AC | 215 ms
16,192 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 3 ms
6,944 KB |
testcase_10 | AC | 99 ms
13,900 KB |
testcase_11 | AC | 41 ms
10,628 KB |
testcase_12 | AC | 112 ms
14,316 KB |
testcase_13 | AC | 166 ms
20,200 KB |
testcase_14 | AC | 207 ms
20,340 KB |
testcase_15 | AC | 190 ms
20,368 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 43 ms
6,944 KB |
testcase_18 | AC | 59 ms
7,168 KB |
testcase_19 | AC | 91 ms
12,636 KB |
testcase_20 | AC | 183 ms
16,584 KB |
testcase_21 | AC | 165 ms
15,640 KB |
testcase_22 | AC | 213 ms
17,580 KB |
testcase_23 | AC | 157 ms
11,648 KB |
testcase_24 | AC | 147 ms
12,416 KB |
testcase_25 | AC | 105 ms
9,344 KB |
testcase_26 | AC | 59 ms
8,576 KB |
testcase_27 | AC | 148 ms
14,932 KB |
testcase_28 | AC | 82 ms
12,304 KB |
testcase_29 | AC | 66 ms
11,552 KB |
testcase_30 | AC | 57 ms
8,448 KB |
testcase_31 | AC | 205 ms
15,252 KB |
testcase_32 | AC | 276 ms
20,408 KB |
testcase_33 | AC | 276 ms
20,324 KB |
testcase_34 | AC | 273 ms
20,364 KB |
testcase_35 | AC | 256 ms
20,296 KB |
testcase_36 | AC | 256 ms
20,316 KB |
ソースコード
#ifdef LOCAL //#define _GLIBCXX_DEBUG #endif //#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll, ll> P; typedef pair<int, int> Pi; typedef vector<ll> Vec; typedef vector<int> Vi; typedef vector<string> Vs; typedef vector<char> Vc; typedef vector<P> VP; typedef vector<vector<ll>> VV; typedef vector<vector<int>> VVi; typedef vector<vector<char>> VVc; typedef vector<vector<vector<ll>>> VVV; typedef vector<vector<vector<vector<ll>>>> VVVV; #define endl '\n' #define REP(i, a, b) for(ll i=(a); i<(b); i++) #define PER(i, a, b) for(ll i=(a); i>=(b); i--) #define rep(i, n) REP(i, 0, n) #define per(i, n) PER(i, n, 0) const ll INF=1e18+18; const ll MOD=1000000007; #define Yes(n) cout << ((n) ? "Yes" : "No") << endl; #define YES(n) cout << ((n) ? "YES" : "NO") << endl; #define ALL(v) v.begin(), v.end() #define rALL(v) v.rbegin(), v.rend() #define pb(x) push_back(x) #define mp(a, b) make_pair(a,b) #define Each(a,b) for(auto &a :b) #define rEach(i, mp) for (auto i = mp.rbegin(); i != mp.rend(); ++i) #ifdef LOCAL #define dbg(x_) cerr << #x_ << ":" << x_ << endl; #define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;} #define dbgset(st) cerr << #st << ":"<<endl; for (auto i = st.begin(); i != st.end(); ++i) { cerr << *i <<" ";}cerr<<endl; #define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;} #define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl; #else #define dbg(...) #define dbgmap(...) #define dbgset(...) #define dbgarr(...) #define dbgdp(...) #endif #define out(a) cout<<a<<endl #define out2(a,b) cout<<a<<" "<<b<<endl #define vout(v) rep(i,v.size()){cout<<v[i]<<" ";}cout<<endl #define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end()) #define fi first #define se second template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } template<typename T1, typename T2> ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; } template<typename T>istream& operator>>(istream&i,vector<T>&v) {rep(j,v.size())i>>v[j];return i;} // vector template<typename T> ostream &operator<<(ostream &s, const vector<T> &v) { int len=v.size(); for(int i=0; i<len; ++i) { s<<v[i]; if(i<len-1) s<<" "; } return s; } // 2 dimentional vector template<typename T> ostream &operator<<(ostream &s, const vector<vector<T> > &vv) { s<<endl; int len=vv.size(); for(int i=0; i<len; ++i) { s<<vv[i]<<endl; } return s; } template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> struct lazy_segtree { public: int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } lazy_segtree() : lazy_segtree(0) {} lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {} lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) { log = ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); lz = std::vector<F>(size, id()); 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; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } S sml = e(), smr = e(); 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() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template <bool (*g)(S)> int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template <class G> int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(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 (*g)(S)> int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template <class G> int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(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; } void debug(ll n){ #ifdef LOCAL Vec segv; rep(i,n){ segv.pb(prod(i,i+1)); } dbg(segv); #endif } private: int _n, size, log; std::vector<S> d; std::vector<F> lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; using S = long long; using F = long long; const F ID = 8e18; S op(S a, S b){ return std::min(a, b); } S e(){ return INF; } S mapping(F f, S x){ return (f == ID ? x : f); } F composition(F f, F g){ return (f == ID ? g : f); } F id(){ return ID; } int solve(){ ll n; cin>>n; ll Q; cin>>Q; Vec L(Q); Vec R(Q); Vec X(Q); vector<pair<ll,P>> vpp(Q); rep(i,Q){ ll l,r,b; cin>>l>>r>>b; l--; L[i] = l; R[i] = r; X[i] = b; vpp[i] = mp(b,mp(l,r)); } dbg(vpp); sort(ALL(vpp)); vector<S> v(n+1,1); lazy_segtree<S, op, e, F, mapping,composition,id> seg(v); Each(vp, vpp){ auto [val, p] = vp; auto [l, r] = p; seg.apply(l,r, val); } bool ok = true; Each(vp, vpp){ auto [val, p] = vp; auto [l, r] = p; if(seg.prod(l,r) != val){ ok = false; } } if(ok){ rep(i,n){ if(i!=0)cout<<" "; cout<<seg.prod(i,i+1); } cout<<endl; }else{ out(-1); } return 0; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout<<std::setprecision(10); // ll T; // cin>>T; // while(T--) solve(); }