Submission #69851526

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<
    T,                                 // key type
    null_type,                         // mapped type (null for set)
    less<T>,                           // ordering
    rb_tree_tag,                       // underlying tree
    tree_order_statistics_node_update> // enable order-statistics
    ;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<string> vs;

template <typename T>
void debug(const vector<T> &x)
{
    for (const auto &elem : x)
    {
        cout << elem << ' ';
    }
    cout << endl;
}

// =================== CONSTANTS ====================
const ll MOD = 1000000007;
const ll mod9 = 998244353;
const ll INF = numeric_limits<int>::max();

// =================== MACROS ======================
#define fast_cin()                    \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define fr(i, a, b) for (ll i = (a); i < (b); ++i)
#define fo(i, n) for (ll i = (0); i < (n); ++i)
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

// ================= QUERY FUNCTION =================
ll query(ll a, ll b)
{
    cout << "? " << a << " " << b << endl;
    cout.flush();
    ll x;
    cin >> x;
    return x;
}

// ================= SEGMENT TREE ===================
struct SegmentTree
{
    vector<ll> tree;
    int n;

    SegmentTree(int size)
    {
        n = size;
        tree.assign(4 * n, 0); // Change 0 to INF for min, -INF for max
    }

    SegmentTree(const vector<ll> &arr)
    {
        n = arr.size();
        tree.assign(4 * n, 0);
        build(0, 0, n - 1, arr);
    }

    void build(int node, int start, int end, const vector<ll> &arr)
    {
        if (start == end)
        {
            tree[node] = arr[start];
        }
        else
        {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid, arr);
            build(2 * node + 2, mid + 1, end, arr);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    ll query(int node, int start, int end, int l, int r)
    {
        if (r < start || end < l)
            return 0;
        if (l <= start && end <= r)
            return tree[node];
        int mid = (start + end) / 2;
        return query(2 * node + 1, start, mid, l, r) + query(2 * node + 2, mid + 1, end, l, r);
    }

    void update(int node, int start, int end, int idx, ll val)
    {
        if (start == end)
        {
            tree[node] = val;
        }
        else
        {
            int mid = (start + end) / 2;
            if (idx <= mid)
                update(2 * node + 1, start, mid, idx, val);
            else
                update(2 * node + 2, mid + 1, end, idx, val);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
};

// ========================================================
ll fast_pow(ll base, ll exp, ll mod = MOD)
{
    ll res = 1;
    while (exp > 0)
    {
        if (exp % 2 == 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

vector<bool> is_prime;
void sieve(int n)
{
    is_prime.assign(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (is_prime[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
}

void dfs(ll i, ll par, vvll &adj, vll &vis)
{
    vis[i] = 1;
    for (auto &ne : adj[i])
    {
        if (ne != par)
        {
            dfs(ne, i, adj, vis);
        }
    }
}

void solve()
{
    ll n, m, mx = -1;
    cin >> n >> m;
    vll cnt(n, 1);
    set<ll> st;
    fo(i, n) { st.insert(i); }
    while (m--)
    {
        ll x, y, ans = 0;
        cin >> x >> y;
        x--, y--;
        if (mx < x)
        {
            fr(j, mx + 1, x + 1)
            {
                ans += cnt[j];
                cnt[y] += cnt[j];
                cnt[j] = 0;
                st.erase(j);
            }
            mx = x;
        }
        cout << ans << endl;
    }
}

int main()
{
    fast_cin();
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Submission Info

Judge Result