Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(X) (X).begin(), (X).end()
  4. #define ll long long
  5. #define fir first
  6. #define sec second
  7. #define pb push_back
  8.  
  9. #ifdef DEBUG
  10. #define deb(X) X
  11. #define log(X) cout << X << "\n"
  12. #define dump(X) cout << __LINE__ << "L: [" << #X << "] = " << X << "\n"
  13. #else
  14. #define deb(X)
  15. #define log(X)
  16. #define dump(X)
  17. #endif // DEBUG
  18.  
  19. using namespace std;
  20.  
  21. const int nmax = 1e6;
  22.  
  23. vector<vector<ll>> g;
  24. vector<vector<ll>> g1;
  25.  
  26. pair<ll, ll> dfs (ll v, vector<vector<ll>>& graph, map<ll, pair<ll, ll>>& mp) {
  27. if (graph[v].size() == 0) {
  28. return {mp[v].fir, mp[v].sec};
  29. }
  30.  
  31. for (ll i = 0; i < graph[v].size(); i++) {
  32. ll to = graph[v][i];
  33. auto q = dfs(to, graph, mp);
  34. mp[v].fir = min(mp[v].fir, q.fir);
  35. mp[v].sec = max(mp[v].sec, q.sec);
  36. }
  37. return mp[v];
  38. }
  39.  
  40. int main() {
  41. #ifndef DEBUG
  42. freopen("volunteers.in", "r", stdin);
  43. freopen("volunteers.out","w",stdout);
  44. #endif
  45.  
  46. ll n, m, k; cin >> n >> m >> k;
  47. g.resize(m);
  48. g1.resize(k);
  49. map<ll, pair<ll, ll>> mp;
  50. map<ll, pair<ll, ll>> mp1;
  51. for (ll i = 0; i < n; i++) {
  52. ll q, z; cin >> q >> z;
  53. q--; z--;
  54. if (mp.count(q) == 0)
  55. mp[q] = {i, i};
  56. else {
  57. mp[q].fir = min(i, mp[q].fir);
  58. mp[q].sec = max(i, mp[q].sec);
  59. }
  60. if (mp1.count(z) == 0)
  61. mp1[z] = {i, i};
  62. else {
  63. mp1[z].fir = min(i, mp1[z].fir);
  64. mp1[z].sec = max(i, mp1[z].sec);
  65. }
  66. }
  67. for (ll i = 0; i < m - 1; i++) {
  68. ll q; cin >> q;
  69. g[q - 1].pb(i);
  70. }
  71. for (ll i = 0; i < k - 1; i++) {
  72. ll q; cin >> q;
  73. g1[q - 1].pb(i);
  74. }
  75.  
  76. dfs(m - 1, g, mp);
  77. dfs(k - 1, g1, mp1);
  78.  
  79. vector<pair<pair<ll, ll>, ll>> pox;
  80.  
  81. for (auto i: mp) {
  82. // dump(i.fir);
  83. // dump(i.sec.fir);
  84. // dump(i.sec.sec);
  85. pox.pb({{i.sec.fir, 0}, 0});
  86. pox.pb({{i.sec.sec, 1}, 0});
  87. }
  88.  
  89. for (auto i: mp1) {
  90. // dump(i.fir);
  91. // dump(i.sec.fir);
  92. // dump(i.sec.sec);
  93. pox.pb({{i.sec.fir, 0}, 1});
  94. pox.pb({{i.sec.sec, 1}, 1});
  95. }
  96. sort(all(pox));
  97.  
  98. ll u = 0, v = 0, cnt = 0;
  99.  
  100. for (ll i = 0; i < pox.size(); i++) {
  101. auto q = pox[i];
  102. dump(q.fir.fir);
  103. dump(q.fir.sec);
  104. dump(q.sec);
  105. if (q.fir.sec == 1) {
  106. if (q.sec == 0)
  107. u--;
  108. else
  109. v--;
  110. continue;
  111. }
  112. if (q.sec == 0) {
  113. u++;
  114. cnt += v;
  115. } else {
  116. v++;
  117. cnt += u;
  118. }
  119. }
  120. cout << cnt;
  121. return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement