fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int find_parent(vector<int>& parent, int x) {
  5.     int r = x;
  6.     while (parent[r] != r) r = parent[r];
  7.     while (parent[x] != r) {
  8.         int nxt = parent[x];
  9.         parent[x] = r;
  10.         x = nxt;
  11.     }
  12.     return r;
  13. }
  14.  
  15. int main() {
  16.     ios::sync_with_stdio(false);
  17.     cin.tie(nullptr);
  18.  
  19.     int N, Q;
  20.     cin >> N >> Q;
  21.  
  22.     vector<long long> cnt(N + 2, 0);
  23.     for (int v = 1; v <= N; ++v) cnt[v] = 1;
  24.     cnt[N + 1] = 0;
  25.  
  26.     vector<int> parent(N + 2);
  27.     for (int v = 1; v <= N + 1; ++v) parent[v] = v;
  28.  
  29.     for (int i = 0; i < Q; ++i) {
  30.         int X, Y;
  31.         cin >> X >> Y;
  32.         long long res = 0;
  33.         int v = find_parent(parent, 1);
  34.         while (v <= X) {
  35.             res += cnt[v];
  36.             cnt[Y] += cnt[v];
  37.             cnt[v] = 0;
  38.             parent[v] = find_parent(parent, v + 1);
  39.             v = parent[v];
  40.         }
  41.         cout << res << '\n';
  42.     }
  43. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
8 5
2 6
3 5
1 7
5 7
7 8
stdout 
2
1
0
3
7
https://ideone.com/s43h1M
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 days 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!