結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー |
|
提出日時 | 2024-02-23 21:39:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 206 ms / 2,500 ms |
コード長 | 5,719 bytes |
コンパイル時間 | 3,339 ms |
コンパイル使用メモリ | 257,540 KB |
実行使用メモリ | 16,128 KB |
最終ジャッジ日時 | 2024-09-29 05:53:51 |
合計ジャッジ時間 | 9,683 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops")#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;#if __cplusplus >= 202002Lusing namespace numbers;#endif// B: coordinate type, C: color typetemplate<class B, class C>struct colorful_interval_set{map<array<B, 2>, C> data;colorful_interval_set(C initial_color = {}): data({{{numeric_limits<B>::min(), numeric_limits<B>::max()}, initial_color}}){ }colorful_interval_set(const map<array<B, 2>, C> &data): data(data){ assert(is_valid(data)); }// is_valid(*this) holds after all operationsstatic bool is_valid(const map<array<B, 2>, C> &data){if(data.empty() || data.begin()->first[0] != numeric_limits<B>::min() || data.rbegin()->first[1] != numeric_limits<B>::max()) return false;for(auto it = data.begin(); next(it) != data.end(); ++ it) if(it->first[1] != next(it)->first[0] || it->second == next(it)->second) returnfalse;return true;}auto belongs(B p){return prev(data.upper_bound({p, numeric_limits<B>::max()}));}// Cover the range [ql, qr) with the color c// process(l, r, pc): color of non-empty range [l, r) is changed from pc to c// The set of intervals [l, r) accessed by process() forms a partition of [ql, qr) in order of increasing l// Amortized O(1) process callsoptional<typename map<array<B, 2>, C>::iterator>cover(B ql, B qr, C c, auto process){assert(ql <= qr);if(ql == qr) return {};array<B, 2> I{ql, ql};auto it = data.lower_bound(I);if(it != data.begin() && ql < prev(it)->first[1]){it = prev(it);auto x = *it;it = data.erase(it);data.insert(it, {{x.first[0], ql}, x.second});it = data.insert(it, {{ql, x.first[1]}, x.second});}while(it != data.end() && it->first[0] < qr){if(qr < it->first[1]){auto x = *it;it = data.erase(it);it = data.insert(it, {{x.first[0], qr}, x.second});data.insert(next(it), {{qr, x.first[1]}, x.second});}process(it->first[0], min(qr, it->first[1]), it->second);I = {min(I[0], it->first[0]), max(I[1], it->first[1])};it = data.erase(it);}if(it != data.begin() && prev(it)->second == c){I[0] = prev(it)->first[0];data.erase(prev(it));}if(it != data.end() && it->second == c){I[1] = it->first[1];it = data.erase(it);}return data.insert(it, {I, c});}optional<typename map<array<B, 2>, C>::iterator>cover(B ql, B qr, C c){return cover(ql, qr, c, [&](B, B, C){ });}// new_color(l, r, c): returns the new color for the non-empty range [l, r), previously colored with c// The set of intervals [l, r) accessed by new_color() forms a partition of [ql, qr) in order of increasing l// O(Number of color ranges affected)void recolor(B ql, B qr, auto new_color){assert(ql <= qr);if(ql == qr) return;auto it = data.lower_bound({ql, ql});if(it != data.begin() && ql < prev(it)->first[1]){it = prev(it);auto [inter, c] = *it;it = data.erase(it);data.insert(it, {{inter[0], ql}, c});it = data.insert(it, {{ql, inter[1]}, c});}while(it != data.end() && it->first[0] < qr){if(qr < it->first[1]){auto x = *it;it = data.erase(it);it = data.insert(it, {{x.first[0], qr}, x.second});data.insert(next(it), {{qr, x.first[1]}, x.second});}it->second = new_color(it->first[0], it->first[1], it->second);if(it != data.begin() && prev(it)->second == it->second){array<B, 2> I{prev(it)->first[0], it->first[1]};C c = it->second;data.erase(prev(it));it = data.erase(it);it = data.insert(it, {I, c});}++ it;}if(it != data.begin() && it != data.end() && prev(it)->second == it->second){array<B, 2> I{prev(it)->first[0], it->first[1]};C c = it->second;data.erase(prev(it));it = data.erase(it);it = data.insert(it, {I, c});}}friend ostream &operator<<(ostream &out, const colorful_interval_set &cis){out << "{";for(auto it = cis.data.begin(); it != cis.data.end(); ++ it){auto [inter, c] = *it;auto [l, r] = inter;out << "[" << l << ", " << r << "){" << c << "}";if(next(it) != cis.data.end()) out << ", ";}return out << "}";}// new_color(l, r, c, d): returns the new color for the non-empty range [l, r), where s is colored with c and t is colored with d// The set of intervals [l, r) accessed by new_color() forms a partition of [INT_MIN, INT_MAX] in order of increasing l// O(Number of color ranges affected)friend colorful_interval_set merge(const colorful_interval_set &s, const colorful_interval_set &t, auto new_color){map<array<B, 2>, C> res;for(auto it_s = s.data.begin(), it_t = t.data.begin(); it_s != s.data.end() && it_t != t.data.end(); ){B l = max(it_s->first[0], it_t->first[0]), r;C c;if(it_s->first[1] <= it_t->first[1]){r = it_s->first[1];if(l == r){++ it_s;continue;}c = new_color(l, r, it_s->second, it_t->second);++ it_s;}else{r = it_t->first[1];if(l == r){++ it_t;continue;}c = new_color(l, r, it_s->second, it_t->second);++ it_t;}if(!res.empty() && res.rbegin()->second == c){l = res.rbegin()->first[0];res.erase(prev(res.end()));}res.insert(res.end(), {{l, r}, c});}return res;}};int main(){cin.tie(0)->sync_with_stdio(0);cin.exceptions(ios::badbit | ios::failbit);int n, len;cin >> n >> len;colorful_interval_set<int, int> cis{-1};vector<int> pos(n);copy_n(istream_iterator<int>(cin), n, pos.begin());int qn;cin >> qn;for(auto qi = 0; qi < qn; ++ qi){int l, r;cin >> l >> r, ++ r;cis.cover(l, r, qi + 1);}for(auto x: pos){cout << cis.belongs(x)->second << "\n";}return 0;}/**/