SHARE
TWEET

Untitled

a guest Nov 9th, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. // Created by willj on 11/2/2019.
  3. //
  4.  
  5. #include <iostream>
  6. #include <fstream>
  7.  
  8. #define MAX_N 100000
  9.  
  10. using namespace std;
  11.  
  12. pair<long long, long long> count = make_pair(0, 0);
  13.  
  14. struct YNode {
  15.     int val;
  16.     YNode *c[2];
  17.     YNode() {
  18.         val = 0;
  19.         c[0] = c[1] = NULL;
  20.     }
  21.     YNode* getC(int i) {
  22.         if (!c[i]) {
  23.             c[i] = new YNode();
  24.         }
  25.         return c[i];
  26.     }
  27.     void add(int y, int v, int a = 0, int b = MAX_N + 10) {
  28.         count.second++;
  29.         val += v;
  30.         if (a == b) return;
  31.         int mid = (a + b) / 2;
  32.         if (y <= mid) getC(0)->add(y, v, a, mid);
  33.         else getC(1)->add(y, v, mid + 1, b);
  34.     }
  35.     int query(int y1, int y2, int a = 0, int b = MAX_N + 10) {
  36.         count.first++;
  37.         if (a >= y1 && b <= y2) {
  38.             return val;
  39.         }
  40.         if (a > y2 || b < y1) return 0;
  41.         int mid = (a + b) / 2;
  42.         return (c[0] != NULL ? c[0]->query(y1, y2, a, mid) : 0) +
  43.                (c[1] != NULL ? c[1]->query(y1, y2, mid + 1, b) : 0);
  44.     }
  45. };
  46. struct XNode {
  47.     YNode* val;
  48.     XNode* c[2];
  49.     XNode() {
  50.         val = new YNode();
  51.         c[0] = c[1] = NULL;
  52.     }
  53.     XNode* getC(int i) {
  54.         if (!c[i]) {
  55.             c[i] = new XNode();
  56.         }
  57.         return c[i];
  58.     }
  59.     void add(int x, int y, int v, int a = 0, int b = MAX_N + 10) {
  60.         count.second++;
  61.         val->add(y, v);
  62.         if (a == b) return;
  63.         int mid = (a + b) / 2;
  64.         if (x <= mid) getC(0)->add(x, y, v, a, mid);
  65.         else getC(1)->add(x, y, v, mid + 1, b);
  66.     }
  67.     int query(int x1, int y1, int x2, int y2, int a = 0, int b = MAX_N + 10) {
  68.         count.first++;
  69.         if (a >= x1 && b <= x2) return val->query(y1, y2);
  70.         if (a > x2 || b < x1) return 0;
  71.         int mid = (a + b) / 2;
  72.         return (c[0] != NULL ? c[0]->query(x1, y1, x2, y2, a, mid) : 0) +
  73.                (c[1] != NULL ? c[1]->query(x1, y1, x2, y2, mid + 1, b) : 0);
  74.     }
  75. };
  76.  
  77. int cow[MAX_N + 1][2];
  78. int pos[MAX_N + 1][2];
  79.  
  80. int main() {
  81.     ios_base::sync_with_stdio(false);
  82.     ifstream cin("src/competition/test.in");
  83.     ofstream cout("src/competition/test.out");
  84.  
  85.     int n, k; cin >> n >> k;
  86.     for (int j = 0; j < 2; j++) {
  87.         for (int i = 0; i < n; i++) {
  88.             cin >> cow[i][j]; cow[i][j]--;
  89.             pos[cow[i][j]][j] = i;
  90.         }
  91.     }
  92.  
  93.     int tot = 0;
  94.     XNode root;
  95.     for (int i = 0; i < n; i++) {
  96.         tot += root.query(0, pos[i][1], pos[i][0], n + 1);
  97.         tot += root.query(pos[i][0], 0, n + 1, pos[i][1]);
  98.         root.add(pos[i][0], pos[i][1], 1);
  99.     }
  100.     for (int i = 0; i < n; i++) {
  101.         root.add(pos[i][0], pos[i][1], -1);
  102.     }
  103.  
  104.     int res = 0;
  105.     for (int i = 0; i < n; i++) {
  106.         res += root.query(0, pos[i][1], pos[i][0], n + 1);
  107.         res += root.query(pos[i][0], 0, n + 1, pos[i][1]);
  108.         root.add(pos[i][0], pos[i][1], 1);
  109.         if (i - k >= 0) root.add(pos[i - k][0], pos[i - k][1], -1);
  110.     }
  111.  
  112.     cout << tot - res << endl;
  113.     cout << count.first << " " << count.second << endl;
  114.     return 0;
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top