結果
問題 |
No.1675 Strange Minimum Query
|
ユーザー |
![]() |
提出日時 | 2021-09-10 22:28:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 432 ms / 2,000 ms |
コード長 | 4,105 bytes |
コンパイル時間 | 1,765 ms |
コンパイル使用メモリ | 132,324 KB |
最終ジャッジ日時 | 2025-01-24 11:32:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <iostream> #include <map> #include <vector> #include <algorithm> #include <numeric> #include <cassert> #include <cmath> #include <queue> #include <set> #include <unordered_map> #include <unordered_set> #include <functional> #define rep(i,n,s) for(int i = (s); i < int(n); i++) #define MM << " " << #define all(x) x.begin(), x.end() template<class T> using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>; using ll = long long; using Pii = std::pair<int, int>; using Pll = std::pair<ll, ll>; template<class T> bool chmin(T& a, const T b) { if(a > b) { a = b; return true; } else { return false; } } template<class T> bool chmax(T& a, const T b) { if(a < b) { a = b; return true; } else { return false; } } template<class T> void vdeb(std::vector<T> &da) { auto n = da.size(); for(size_t i = 0; i < n; i++) { if(i == n-1) std::cout << da[i] << std::endl; else std::cout << da[i] << " "; } } template<> void vdeb(std::vector<std::string> &da) { auto n = da.size(); for(size_t i = 0; i < n; i++) { std::cout << da[i] << std::endl; } } template<typename T> struct SegTree{ std::vector<T> nod; T t0; std::function<T(T,T)> operation; std::function<T(T,T)> merge; int size; SegTree(int _size, T _t0, std::function<T(T,T)> _operation, std::function<T(T,T)> _merge):t0(_t0), operation(_operation), merge(_merge){ size=1; while(_size>size){ size*=2; } nod=std::vector<T>(size*2-1, t0); } void update(int k, T a){ // operation(da[k], a) assert(0<= k && k < size); k+=size-1; nod[k] = operation(nod[k], a); while(k>0){ k=(k-1)/2; nod[k] = merge(nod[k*2+1], nod[k*2+2]); } } void range_update(int a, int b, T x) { assert(0 <= a && a < size); assert(0 <= b && b <= size); assert(a <= b); range_update_query(a, b, 0, 0, size, x); } T sum(int a, int b) { // merge[a, b) assert(0 <= a && a < size); assert(0 <= b && b <= size); assert(a <= b); return sum_query(a, b, 0, 0, size); } void deb(){ for(int i=0;i<size*2-1;i++){ if(i==size*2-2) std::cout << nod[i] <<std:: endl; else std::cout << nod[i] << ' '; } return; } private: void range_update_query(int a,int b,int k,int l,int r,T x){ if(r<=a||b<=l){ return; } if(a<=l && r<=b){ nod[k] = operation(nod[k], x); return; } else{ range_update_query(a,b,k*2+1,l,(l+r)/2,x); range_update_query(a,b,k*2+2,(l+r)/2,r,x); return; } } T sum_query(int a,int b,int k,int l,int r){ if(r<=a||b<=l){ return t0; } if(a<=l && r<=b){ return nod[k]; } else{ return merge(sum_query(a,b,k*2+1,l,(l+r)/2),sum_query(a,b,k*2+2,(l+r)/2,r)); } } }; using namespace std; int main() { int n, q; cin >> n >> q; vector<vector<Pii>> da(n+1); vector<pair<Pii, int>> query(q); rep(i,q,0) { int l, r, b; cin >> l >> r >> b; da[l-1].push_back({b, 0}); da[r].push_back({b, 1}); query[i] = {{l-1, r}, b}; } SegTree<int> st(n, 1000000000, [](int x, int y){return min(x, y);}, [](int x, int y){return min(x, y);}); map<int, int> mp; rep(i,n,0) { for(auto &j : da[i]) { if(j.second) { mp[j.first]--; if(mp[j.first] == 0) mp.erase(j.first); } else { mp[j.first]++; } } if(!mp.empty()) st.update(i, (--mp.end())->first); } rep(i,q,0) { if(st.sum(query[i].first.first, query[i].first.second) != query[i].second) { cout << -1 << endl; return 0; } } vector<int> ans(n); rep(i,n,0) ans[i] = st.sum(i, i+1); vdeb(ans); }