-
Notifications
You must be signed in to change notification settings - Fork 5
Expand file tree
/
Copy pathE.cpp
More file actions
84 lines (77 loc) · 2.09 KB
/
Copy pathE.cpp
File metadata and controls
84 lines (77 loc) · 2.09 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define all(x) x.begin(), x.end()
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
#define curtime chrono::steady_clock::now().time_since_epoch().count
#define rep(i, beg, n, s) for (int i = beg; i < n; i += s)
const double PI = acos(-1);
using namespace std;
inline int mod(int n, int m) {
int ret = n % m;
if (ret < 0) ret += m;
return ret;
}
int gcd(int a, int b) {
if (a == 0)
return b;
else
return gcd(b % a, a);
}
vector<set<ii, greater<ii>>> kinders(212345);
set<ii> ans;
void solution() {
int n, q;
cin >> n >> q;
int child[n + 1];
int kinder[n + 1];
for (int i = 1; i <= n; i++) {
cin >> child[i] >> kinder[i];
if (kinders[kinder[i]].size() > 0)
ans.erase(ii(kinders[kinder[i]].begin()->ff, kinder[i]));
kinders[kinder[i]].insert(ii(child[i], i));
ans.insert(ii(kinders[kinder[i]].begin()->ff, kinder[i]));
}
while (q--) {
int c, d;
cin >> c >> d;
ans.erase(ii(kinders[kinder[c]].begin()->ff, kinder[c]));
kinders[kinder[c]].erase(ii(child[c], c));
if (kinders[kinder[c]].size() > 0) {
ans.insert(ii(kinders[kinder[c]].begin()->ff, kinder[c]));
}
kinder[c] = d;
if (kinders[kinder[c]].size() > 0) {
ans.erase(ii(kinders[kinder[c]].begin()->ff, kinder[c]));
}
kinders[kinder[c]].insert(ii(child[c], c));
ans.insert(ii(kinders[kinder[c]].begin()->ff, kinder[c]));
// for (ii x : kinders[2]) cout << "-> " << x.ff << " " << x.ss << endl;
// for (ii x : ans) cout << x.ff << " " << x.ss << endl;
cout << ans.begin()->ff << endl;
}
}
int32_t main() {
DESYNC;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int t = 1;
#ifdef MULTIPLE_TEST_CASE
cin >> t;
#endif
while (t--) solution();
}