fork download
copy 
  1. #pragma GCC optimize ("O3")
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define llong long long 
  7. #define len(x) ((int)x.size())
  8. #define rep(i,n) for (int i = -1; ++ i < n; )
  9. #define rep1(i,n) for (int i = 0; i ++ < n; )
  10. #define rand __rand
  11. mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
  12. template<class T = int> T rand(T range = numeric_limits<T>::max()) { return (T)(rng() % range); }
  13.  
  14. #define CONCAT_(x, y) x##y/*{{{*/
  15. #define CONCAT(x, y) CONCAT_(x, y)
  16. #define SPEC(name) CONCAT(name, __LINE__)
  17. #ifdef LOCAL_DEBUG   
  18. int __db_level = 0;
  19. #define clog cerr << string(__db_level * 2, ' ')
  20. struct debug_block {
  21.     string msg;
  22.     debug_block(const string& s): msg(s) { clog << "{ " << msg << endl; ++__db_level; }
  23.     ~debug_block() { --__db_level; clog << "} " << msg << endl; }
  24. };
  25. #define DB(args...) stringstream SPEC(ss); SPEC(ss)<< args; debug_block SPEC(dbbl)(SPEC(ss).str())
  26. #else
  27. #define clog if (0) cerr
  28. #define DB(...)
  29. #endif
  30. #define db(val) "[" #val " = " << val << "]; "
  31. template<class U, class V> ostream& operator<<(ostream& out, const pair<U, V>& p) {
  32.     return out << "(" << p.first << ", " << p.second << ")";
  33. }
  34. template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
  35.     if (i == tuple_size<T>::value) return out << ")";
  36.     else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup);
  37. }
  38. template<class ...U>
  39. ostream& operator<<(ostream& out, const tuple<U...>& tup) { return print_tuple_utils<0, tuple<U...>>(out, tup); }
  40. template<class, typename = void> struct has_const_iterator : false_type {};
  41. template<class T> struct has_const_iterator<T, void_t<typename T::const_iterator>> : true_type {};
  42. template<class T>
  43. typename enable_if<has_const_iterator<T>::value && !is_same<T, string>::value, ostream&>::type
  44. operator<<(ostream& out, const T& container) { 
  45.     auto beg = container.begin(), end = container.end();
  46.     out << "(" << container.size() << ") {";
  47.     if (beg != end) out << *(beg++);
  48.     while (beg != end) out << ", " << *(beg++);
  49.     return out << "}";
  50. }
  51. /*}}}*/
  52. // ACTUAL SOLUTION BELOW ////////////////////////////////////////////////////////////
  53.  
  54. const int maxn = 500010;
  55. const int maxm = 1000000 + 10;
  56. struct Query {
  57.     int type, l, r, h;
  58.     int ans;
  59.     Query() {}
  60.     void upd_ans(int oh) {
  61.         ans = min(ans, abs(h - oh));
  62.     }
  63. };
  64.  
  65. int n, m;
  66. Query qr[maxm];
  67. vector<int> sorted_values[maxn * 2], sorted_times[maxn * 2];
  68.  
  69. void add_point(vector<int>* cont, int p, int id) {
  70.     for (cont[p += n].push_back(id); p > 1; p >>= 1) cont[p >> 1].push_back(id);
  71. }
  72.  
  73. void add_range(vector<int>* cont, int l, int r, int id) {
  74.     for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  75.         if (l & 1) cont[l++].push_back(id);
  76.         if (r & 1) cont[--r].push_back(id);
  77.     }
  78. }
  79.  
  80. int cnt[maxm], dsu[maxm];
  81. int find_set(int u) {
  82.     return dsu[u] < 0 ? u : dsu[u] = find_set(dsu[u]);
  83. }
  84.  
  85. int join(int u, int v) {
  86.     u = find_set(u);
  87.     v = find_set(v);
  88.     if (u == v) return u;
  89.     if (-dsu[u] < -dsu[v]) swap(u, v);
  90.     dsu[u] += dsu[v];
  91.     dsu[v] = u;
  92.     cnt[u] += cnt[v];
  93.     return u;
  94. }
  95.  
  96. void cal_ans_then_clear(int node) {
  97.     DB(db(node));
  98.     static int left[maxm], right[maxm];
  99.     auto& sv = sorted_values[node], &st = sorted_times[node];
  100.     clog << db(sv) << endl; 
  101.     clog << db(st) << endl; 
  102.     assert(len(sv) == len(st));
  103.     int prv = -1;
  104.     for (auto i: sv) {
  105.         dsu[i] = -1;
  106.         cnt[i] = 1;
  107.         left[i] = prv;
  108.         if (prv != -1) right[prv] = i;
  109.         prv = i;
  110.     }
  111.     if (prv != -1) right[prv] = -1;
  112.  
  113.     reverse(st.begin(), st.end());
  114.     for (auto i: st) {
  115.         clog << db(i) << endl; 
  116.         int cur = find_set(i);
  117.         if (qr[i].type == 1) {
  118.             while (left[cur] != -1 and qr[left[cur]].type == 1) {
  119.                 clog << "left " << db(cur) << db(left[cur]) << db(right[cur]) << endl;  
  120.                 assert(find_set(cur) != find_set(left[cur]));
  121.                 int ol = left[cur], oc = cur;
  122.                 cur = join(cur, ol);
  123.                 left[cur] = left[ol];
  124.                 right[cur] = right[oc];
  125.                 if (left[cur] != -1) right[left[cur]] = cur;
  126.                 if (right[cur] != -1) left[right[cur]] = cur;
  127.             }
  128.             while (right[cur] != -1 and qr[right[cur]].type == 1) {
  129.                 clog << "right " << db(cur) << db(left[cur]) << db(right[cur]) << endl;  
  130.                 assert(find_set(cur) != find_set(right[cur]));
  131.                 int oldr = right[cur], oc = cur;
  132.                 cur = join(cur, oldr);
  133.                 left[cur] = left[oc];
  134.                 right[cur] = right[oldr];
  135.                 if (left[cur] != -1) right[left[cur]] = cur;
  136.                 if (right[cur] != -1) left[right[cur]] = cur;
  137.             }
  138.  
  139.             if (left[cur] != -1) {
  140.                 qr[i].upd_ans(qr[left[cur]].h);
  141.             }
  142.             if (right[cur] != -1) {
  143.                 qr[i].upd_ans(qr[right[cur]].h);
  144.             }
  145.         }
  146.         --cnt[cur];
  147.         if (cnt[cur]) continue;
  148.         if (left[cur] != -1) right[left[cur]] = right[cur];
  149.         if (right[cur] != -1) left[right[cur]] = left[cur];
  150.     }
  151.  
  152.     sv.clear();
  153.     st.clear();
  154.     clog << db(sv) << endl;
  155.     clog << db(st) << endl;
  156. }
  157.  
  158. // #define testing    
  159. int main(void) {
  160.     rng.seed(177013);
  161.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  162.  
  163. #ifndef testing
  164.     int ntest; cin >> ntest;
  165. #else
  166.     int ntest = 10000;
  167. #endif
  168.     while (ntest--) {
  169. #ifndef testing
  170.         cin >> n >> m;
  171. #else
  172.         n = 10; m = 10;
  173.         vector<int> pos_for_0(n);
  174.         rep(i, n) pos_for_0[i] = i + 1;
  175.         shuffle(pos_for_0.begin(), pos_for_0.end(), rng);
  176. #endif
  177.         n += 10;
  178.         rep(i, m) {
  179.             int qr_type, qr_l, qr_r = -1, qr_h;
  180. #ifndef testing
  181.             cin >> qr_type;
  182.             if (qr_type) cin >> qr_l >> qr_r >> qr_h;
  183.             else cin >> qr_l >> qr_h;
  184. #else
  185.             qr_type = (len(pos_for_0) ? rand(2) : 1);
  186.             if (qr_type == 0) {
  187.                 qr_l = pos_for_0.back();
  188.                 pos_for_0.pop_back();
  189.             } else {
  190.                 qr_l = rand(n) + 1;
  191.                 qr_r = rand(n) + 1;
  192.                 if (qr_l > qr_r) swap(qr_l, qr_r);
  193.             }
  194.             qr_h = rand(1000000000) + 1;
  195. #endif
  196.  
  197.             qr[i].type = qr_type;
  198.             qr[i].l = qr_l - 1;
  199.             qr[i].r = qr_r;
  200.             qr[i].h = qr_h;
  201.             qr[i].ans = INT_MAX;
  202.         }
  203.  
  204.         clog << "Add by times" << endl;
  205.         rep(i, m) {
  206.             // clog << db(i) << endl; 
  207.             if (qr[i].type == 0) add_point(sorted_times, qr[i].l, i);
  208.             else add_range(sorted_times, qr[i].l, qr[i].r, i);
  209.         }
  210.  
  211.         clog << "Sorting" << endl;
  212.         vector<int> pos(m);
  213.         rep(i, m) pos[i] = i;
  214.         sort(pos.begin(), pos.end(), [&](int u, int v) { return qr[u].h < qr[v].h; });
  215.         clog << "Add by values" << endl;
  216.         for (auto i: pos) {
  217.             // clog << db(i) << endl; 
  218.             if (qr[i].type == 0) add_point(sorted_values, qr[i].l, i);
  219.             else add_range(sorted_values, qr[i].l, qr[i].r, i);
  220.         }
  221.         pos.clear();
  222.  
  223.  
  224.         rep(i, 2 * n) cal_ans_then_clear(i);
  225. #ifndef testing
  226.         rep(i, m) {
  227.             if (qr[i].type == 0) continue;
  228.             if (qr[i].ans >= INT_MAX) cout << "-1\n";
  229.             else cout << qr[i].ans << '\n';
  230.         }
  231. #else
  232.         cout << "OK" << endl;
  233. #endif
  234.     }
  235.  
  236.  
  237.     return 0;
  238. }
  239.  
  240. // Remember:
  241. // - Multitest? REFRESHING the data!!!
  242. // - Constrains for each set of data may differs. Should NOT USE the same max constant (maxn)
  243. //   for all of them.
  244. // vim: foldmethod=marker
  245.  
Success #stdin #stdout 0.02s 50440KB
comments (?)
stdin
copy 
1
3 5
1 1 3 2
0 1 1
0 3 3
1 1 2 2
1 2 3 2
stdout
copy 
-1
1
1
https://ideone.com/oNh601
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!