Submission #59865604

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<char> vchar;
typedef vector <pair<ll, ll>> vp;
typedef pair<ll, ll> pll;
typedef map <ll, ll> mll;
typedef set <ll> sll;
#define pb push_back
#define ff first
#define ss second
#define str to_string
#define all(x) (x).begin(), (x).end()
#define print(x) for (auto i : x) cout << i << ' '; cout << '\n';
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define TxtIO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<char> vchar;
typedef vector <pair<ll, ll>> vp;
typedef pair<ll, ll> pll;
typedef map <ll, ll> mll;
typedef set <ll> sll;
#define pb push_back
#define ff first
#define ss second
#define str to_string
#define all(x) (x).begin(), (x).end()
#define print(x) for (auto i : x) cout << i << ' '; cout << '\n';
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define TxtIO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

const ll maxn = 3*1e6+5;
const ll mod = 1e9+7;
const ll inf = 1e12;

ll pw(ll a, ll b, ll M = mod) {ll ans = 1; for (; b; a = ((a * a) % M), b >>= 1) if (b & 1) ans = (ans * a) % M; return ans;}

ll n, q, t, x, c;
ll cnt[maxn];

int main() {
    cin >> n >> q;
    set <pll> st;
    for (ll i = 1; i <= n; i++) {
        cnt[i] = 1;
        st.insert({i, i});
    }

    st.insert({n+1, 0});

    while (q--) {
        cin >> t;
        if (t == 1) {
            cin >> x >> c;

            auto it = st.upper_bound({x, inf});
            auto it2 = st.upper_bound({x, inf});
            it2--;

            if ((*it2).ss != c) {
                ll f = (*it2).ff;
                cnt[(*it2).ss] -= (it)->ff - (it2)->ff;
                cnt[c] += (it)->ff - (it2)->ff;
                st.erase(it2);
                st.insert({f, c});
                if ((it)->ss == c) {
                    st.erase(it);
                }
                auto it3 = it2;
                if (it3 != st.begin()) {
                    it3--;
                    if ((it3)->ss == c) {
                        st.erase(it2);
                    }
                }
            }

//            cout << (it2)->ff << ' ' << (it)->ff << '\n';
//            for (ll i = 1; i <= n; i++) cout << cnt[i] << ' ';cout << '\n';

        } else {
            cin >> c;
            cout << cnt[c] << '\n';
        }


    }

    return 0;
}

Submission Info

Judge Result