fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 1000007;
  6. map<int, int> me;
  7. vector<int> st[maxn];
  8.  
  9. int merg(int a, int b)
  10. {
  11.     auto it1 = --me.upper_bound(a);
  12.     auto it2 = --me.upper_bound(b);
  13.     a = it1->second;
  14.     b = it2->second;
  15.     if(a == b)
  16.         return b;
  17.     if(st[a].size() > st[b].size())
  18.         swap(a, b);
  19.     for(auto it: st[a])
  20.         if(me.count(it))
  21.             me[it] = b;
  22.     for(auto it: st[a])
  23.     {
  24.         auto IT = --me.upper_bound(it);
  25.         if(IT->first != it)
  26.             continue;
  27.         st[b].push_back(it);
  28.         auto IT2 = IT;
  29.         IT2++;
  30.         while(IT2->second == IT->second)
  31.             IT2 = me.erase(IT2);
  32.         IT2 = IT;
  33.         IT2--;
  34.         if(IT2->second == IT->second)
  35.             me.erase(IT);
  36.     }
  37.     return b;
  38. }
  39.  
  40. int main()
  41. {
  42.     //freopen("input.txt", "r", stdin);
  43.     //freopen("output.txt", "w", stdout);
  44.     ios::sync_with_stdio(0);
  45.     cin.tie(0);
  46.     int n, q;
  47.     cin >> n >> q;
  48.     for(int i = 0; i <= n + 1; i++)
  49.         me[i] = i;
  50.     for(int i = 0; i <= n + 1; i++)
  51.         st[i].push_back(i);
  52.     while(q--)
  53.     {
  54.         int t;
  55.         cin >> t;
  56.         if(t == 1)
  57.         {
  58.             int a, b;
  59.             cin >> a >> b;
  60.             merg(a, b);
  61.         }
  62.         if(t == 2)
  63.         {
  64.             int a, b;
  65.             cin >> a >> b;
  66.             vector<int> que;
  67.             auto it = --me.upper_bound(a);
  68.             while(it->first <= b)
  69.                 que.push_back((it++)->second);
  70.             b = que[0];
  71.             for(int i = 1; i < que.size(); i++)
  72.                 b = merg(b, que[i]);
  73.         }
  74.         if(t == 3)
  75.         {
  76.             int a, b;
  77.             cin >> a >> b;
  78.             auto it1 = --me.upper_bound(a);
  79.             auto it2 = --me.upper_bound(b);
  80.             if(it1->second == it2->second)
  81.                 cout << "YES\n";
  82.             else
  83.                 cout << "NO\n";
  84.         }
  85.     }
  86.     return 0;
  87. }
Time limit exceeded #stdin #stdout 5s 388352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dRjihv
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!