oj.uz

Submission #879710

# Submission time Handle Problem Language Result Execution time Memory
879710 2023-11-27T23:53:15 Z MilosMilutinovic Dragon 2 (JOI17_dragon2) C++14
100 / 100
 1842 ms 77172 KB 
#include <bits/stdc++.h>
 
using namespace std;

#define int long long
 
struct pt {
  int x, y;
  pt(int _x = 0, int _y = 0) : x(_x), y(_y) {}
};
 
bool const operator == (pt a, pt b) {
  return a.x == b.x && a.y == b.y;
}

pt sim(pt a, pt b) {
  return pt(b.x + (b.x - a.x), b.y + (b.y - a.y));
}

int orient(pt a, pt b, pt c) {
  long long val = (b.y - a.y) * 1LL * (c.x - b.x) - (b.x - a.x) * 1LL * (c.y - b.y);
  return (val == 0 ? 0 : (val > 0 ? 1 : -1)); // 1 clock, -1 counterclock
}
 
struct angle {
  pt a, b, c;
};

bool const operator == (angle p, angle q) {
  return p.a == q.a && p.b == q.b && p.c == q.c;
}
 
bool const operator < (angle p, angle q) {
  if (p == q) {
    return false;
  }
  int ps = orient(p.a, p.b, p.c);
  int qs = orient(q.a, q.b, q.c);
  if (orient(p.a, q.a, p.b) == 0) {
    while (true) {

    }
  }
  if (ps == qs) {
    return orient(p.a, q.a, p.b) == ps;
  } else {
    // ...
    while (true) {

    }
    return false;
  }
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pt> p(n);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i].x >> p[i].y >> c[i];
    --c[i];
  }
  pt a, b;
  cin >> a.x >> a.y >> b.x >> b.y;
  vector<vector<vector<int>>> ids(m, vector<vector<int>>(2));
  vector<int> cnt(m);
  for (int i = 0; i < n; i++) {
    int o = orient(a, b, p[i]);
    assert(o != 0);
    int sd = (o == 1 ? 0 : 1);
    ids[c[i]][sd].push_back(i);
    cnt[c[i]] += 1;
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (orient(p[i], p[j], a) == 0) {
        assert(false);
      }
    }
  }
  vector<vector<angle>> all_a(2);
  vector<vector<angle>> all_b(2);
  for (int i = 0; i < n; i++) {
    int o = orient(a, b, p[i]);
    int sd = (o == 1 ? 0 : 1);
    pt p_a = sim(p[i], a);
    pt p_b = sim(p[i], b);
    all_a[sd].push_back({p[i], a, b});
    all_b[sd].push_back({p[i], b, a});
    all_a[sd ^ 1].push_back({p_a, a, b});
    all_b[sd ^ 1].push_back({p_b, b, a});
  }
  for (int sd = 0; sd < 2; sd++) {
    sort(all_a[sd].begin(), all_a[sd].end());
    sort(all_b[sd].begin(), all_b[sd].end());
  }
  vector<int> ia(n);
  vector<int> ib(n);
  vector<int> ja(n);
  vector<int> jb(n);
  for (int i = 0; i < n; i++) {
    int o = orient(a, b, p[i]);
    int sd = (o == 1 ? 0 : 1);
    {
      angle A;
      A.a = p[i];
      A.b = a;
      A.c = b;
      int low = 0, high = (int) all_a[sd].size() - 1;
      while (low <= high) {
        int mid = low + high >> 1;
        if (all_a[sd][mid] == A) {
          ia[i] = mid;
          break;
        } else if (all_a[sd][mid] < A) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      //ia[i] = (int) (lower_bound(all_a[sd].begin(), all_a[sd].end(), A) - all_a[sd].begin());
      assert(A == all_a[sd][ia[i]]);
    }
    {
      angle A;
      A.a = p[i];
      A.b = b;
      A.c = a;
      int low = 0, high = (int) all_b[sd].size() - 1;
      while (low <= high) {
        int mid = low + high >> 1;
        if (all_b[sd][mid] == A) {
          ib[i] = mid;
          break;
        } else if (all_b[sd][mid] < A) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      //ib[i] = (int) (lower_bound(all_b[sd].begin(), all_b[sd].end(), A) - all_b[sd].begin());
      assert(A == all_b[sd][ib[i]]);
    }
    {
      angle A;
      A.a = sim(p[i], a);
      A.b = a;
      A.c = b;
      int low = 0, high = all_a[sd ^ 1].size() - 1;
      while (low <= high) {
        int mid = low + high >> 1;
        if (all_a[sd ^ 1][mid] == A) {
          ja[i] = mid;
          break;
        } else if (all_a[sd ^ 1][mid] < A) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      //ja[i] = (int) (lower_bound(all_a[sd ^ 1].begin(), all_a[sd ^ 1].end(), A) - all_a[sd ^ 1].begin());
      assert(A == all_a[sd ^ 1][ja[i]]);
    }
    {
      angle A;
      A.a = sim(p[i], b);
      A.b = b;
      A.c = a;
      int low = 0, high = all_b[sd ^ 1].size() - 1;
      while (low <= high) {
        int mid = low + high >> 1;
        if (all_b[sd ^ 1][mid] == A) {
          jb[i] = mid;
          break;
        } else if (all_b[sd ^ 1][mid] < A) {
          low = mid + 1;
        } else {
          high = mid - 1;
        }
      }
      //jb[i] = (int) (lower_bound(all_b[sd ^ 1].begin(), all_b[sd ^ 1].end(), A) - all_b[sd ^ 1].begin());     
      assert(A == all_b[sd ^ 1][jb[i]]);
    }
  }
  int q;
  cin >> q;
  vector<int> f(q), g(q);
  for (int i = 0; i < q; i++) {
    cin >> f[i] >> g[i];
    --f[i]; --g[i];
  }
  vector<int> qt(q, -1);
  map<pair<int, int>, int> mp;
  for (int i = 0; i < q; i++) {
    if (mp.count({f[i], g[i]})) {
      //qt[i] = mp[{f[i], g[i]}];
    } else {
      //mp[{f[i], g[i]}] = i;
    }
  }
  vector<int> res(q);
  {
    vector<vector<vector<vector<pair<int, int>>>>> qs(m, vector<vector<vector<pair<int, int>>>>(2));
    for (int i = 0; i < m; i++) {
      qs[i][0].resize(cnt[i]);
      qs[i][1].resize(cnt[i]);
    }
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < 2; j++) {
        sort(ids[i][j].begin(), ids[i][j].end(), [&](int i, int j) {
          return ia[i] < ia[j];
        });
      }
    }
    for (int qq = 0; qq < q; qq++) {
      if (qt[qq] != -1) {
        continue;
      }
      if (min(cnt[f[qq]], cnt[g[qq]]) == 0) {
        continue;
      }
      if (cnt[f[qq]] <= cnt[g[qq]]) {
        for (int sd = 0; sd < 2; sd++) {
          for (int i : ids[f[qq]][sd]) {
            {
              int low = 0, high = (int) ids[g[qq]][sd].size() - 1, pos = -1;
              while (low <= high) {
                int mid = low + high >> 1;
                if (ia[i] >= ia[ids[g[qq]][sd][mid]]) {
                  pos = mid;
                  low = mid + 1;
                } else {
                  high = mid - 1;
                }
              }
              if (pos != -1) {
                qs[g[qq]][sd][pos].emplace_back(qq, ib[i]);
              }
            }
            {
              int low = 0, high = (int) ids[g[qq]][sd ^ 1].size() - 1, pos = -1;
              while (low <= high) {
                int mid = low + high >> 1;
                if (ja[i] >= ia[ids[g[qq]][sd ^ 1][mid]]) {
                  pos = mid;
                  low = mid + 1;
                } else {
                  high = mid - 1;
                }
              }
              if (pos != -1) {
                qs[g[qq]][sd ^ 1][pos].emplace_back(qq, jb[i]);
              }
            }
          }
        }
      }
    }
    vector<int> fenw(n);
    auto Modify = [&](int x, int v) {
      while (x < n) {
        fenw[x] += v;
        x |= (x + 1);
      }
    };
    auto Query = [&](int x) {
      int v = 0;
      while (x >= 0) {
        v += fenw[x];
        x = (x & (x + 1)) - 1;
      }
      return v;
    };
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < 2; j++) {
        int sz = (int) ids[i][j].size();
        for (int k = 0; k < sz; k++) {
          Modify(ib[ids[i][j][k]], +1);
          for (auto& p : qs[i][j][k]) {
            res[p.first] += Query(p.second);
          }
        }
        for (int k = 0; k < sz; k++) {
          Modify(ib[ids[i][j][k]], -1);
        }
      }
    }
  }
  {
    /* vector<vector<vector<vector<pair<int, int>>>>> qs(m, vector<vector<vector<pair<int, int>>>>(2));
    for (int i = 0; i < m; i++) {
      qs[i][0].resize(cnt[i]);
      qs[i][1].resize(cnt[i]);
    }
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < 2; j++) {
        sort(ids[i][j].begin(), ids[i][j].end(), [&](int i, int j) {
          return ia[i] > ia[j];
        });
      }
    }
    for (int qq = 0; qq < q; qq++) {
      if (qt[qq] != -1) {
        continue;
      }
      if (min(cnt[f[qq]], cnt[g[qq]]) == 0) {
        continue;
      }
      if (cnt[f[qq]] > cnt[g[qq]]) {
        for (int sd = 0; sd < 2; sd++) {
          for (int i : ids[g[qq]][sd]) {
            {
              int low = 0, high = (int) ids[f[qq]][sd].size() - 1, pos = -1;
              while (low <= high) {
                int mid = low + high >> 1;
                if (ia[ids[f[qq]][sd][mid]] >= ia[i]) {
                  pos = mid;
                  low = mid + 1;
                } else {
                  high = mid - 1;
                }
              }
              if (pos != -1) {
                qs[f[qq]][sd][pos].emplace_back(qq, ib[i]);
              }
            }
          }
        }
      }
      vector<int> fenw(n);
      auto Modify = [&](int x, int v) {
        assert(0 <= x);
        while (x < n) {
          fenw[x] += v;
          x |= (x + 1);
        }
      };
      auto Query = [&](int x) {
        assert(x < n);
        int v = 0;
        while (x >= 0) {
          v += fenw[x];
          x = (x & (x + 1)) - 1;
        }
        return v;
      };
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < 2; j++) {
          int sz = (int) ids[i][j].size();
          for (int k = 0; k < sz; k++) {
            Modify(ib[ids[i][j][k]], +1);
            for (auto& p : qs[i][j][k]) {
              res[p.first] += Query(n - 1) - Query(p.second - 1);
            }
          }
          for (int k = 0; k < sz; k++) {
            Modify(ib[ids[i][j][k]], -1);
          }
        }
      }
    } */
    for (int qq = 0; qq < q; qq++) {
      if (cnt[f[qq]] > cnt[g[qq]]) {
        for (int sd = 0; sd < 2; sd++) {
          for (int i : ids[f[qq]][sd]) {
            for (int j : ids[g[qq]][sd]) {
              if (ia[i] >= ia[j] && ib[i] >= ib[j]) {
                res[qq] += 1;
              }
            }
          }
        }
      }
    }
  }
  {
    vector<vector<vector<vector<pair<int, int>>>>> qs(m, vector<vector<vector<pair<int, int>>>>(2));
    for (int i = 0; i < m; i++) {
      qs[i][0].resize(cnt[i]);
      qs[i][1].resize(cnt[i]);
    }
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < 2; j++) {
        sort(ids[i][j].begin(), ids[i][j].end(), [&](int x, int y) {
          return ja[x] > ja[y];
        });
      }
    }
    /* for (int qq = 0; qq < q; qq++) {
      if (qt[qq] != -1) {
        continue;
      }
      if (min(cnt[f[qq]], cnt[g[qq]]) == 0) {
        continue;
      }
      if (cnt[f[qq]] > cnt[g[qq]]) {
        for (int sd = 0; sd < 2; sd++) {
          for (int i : ids[g[qq]][sd]) {
            int pos = -1;
            while (pos + 1 < (int) ids[f[qq]][sd ^ 1].size() && ja[ids[f[qq]][sd ^ 1][pos + 1]] >= ia[i]) {
              pos += 1;
            }
            if (pos != -1) {
              qs[f[qq]][sd ^ 1][pos].emplace_back(qq, ib[i]);
            }
            {
              int low = 0, high = (int) ids[f[qq]][sd ^ 1].size() - 1, pos = -1;
              while (low <= high) {
                int mid = low + high >> 1;
                if (ja[ids[f[qq]][sd ^ 1][mid]] >= ia[i]) {
                  pos = mid;
                  low = mid + 1;
                } else {
                  high = mid - 1;
                }
              }
              if (pos != -1) {
                qs[f[qq]][sd ^ 1][pos].emplace_back(qq, ib[i]);
              }
            } 
          }
        }
      }
      vector<int> fenw(n);
      auto Modify = [&](int x, int v) {
        assert(0 <= x);
        while (x < n) {
          fenw[x] += v;
          x |= (x + 1);
        }
      };
      auto Query = [&](int x) {
        assert(x < n);
        int v = 0;
        while (x >= 0) {
          v += fenw[x];
          x = (x & (x + 1)) - 1;
        }
        return v;
      };
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < 2; j++) {
          int sz = (int) ids[i][j].size();
          for (int k = 0; k < sz; k++) {
  //          Modify(jb[ids[i][j][k]], +1);
            for (auto& p : qs[i][j][k]) {
              for (int w = 0; w <= k; w++) {
                if (jb[ids[i][j][w]] >= p.second) {
                  res[p.first] += 1;
                }
              }
//              res[p.first] += Query(n - 1) - Query(p.second - 1);
            }
          }
          for (int k = 0; k < sz; k++) {
    //        Modify(jb[ids[i][j][k]], -1);
          }
        }
      }
    } */
    for (int qq = 0; qq < q; qq++) {
      if (cnt[f[qq]] > cnt[g[qq]]) {
        for (int sd = 0; sd < 2; sd++) {
          for (int i : ids[g[qq]][sd]) {
            for (int j : ids[f[qq]][sd ^ 1]) {
              if (ja[j] < ia[i]) {
                break;
              }
              if (jb[j] >= ib[i]) {
                res[qq] += 1;
              }
            }
          }
        }
      }
    }
  }
  
  for (int i = 0; i < q; i++) {
    if (qt[i] != -1) {
      res[i] = res[qt[i]];
    }
  }
  for (int i = 0; i < q; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:114:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
dragon2.cpp:134:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
dragon2.cpp:154:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  154 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
dragon2.cpp:174:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  174 |         int mid = low + high >> 1;
      |                   ~~~~^~~~~~
dragon2.cpp:231:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  231 |                 int mid = low + high >> 1;
      |                           ~~~~^~~~~~
dragon2.cpp:246:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  246 |                 int mid = low + high >> 1;
      |                           ~~~~^~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1472 KB Output is correct
2 Correct 19 ms 1536 KB Output is correct
3 Correct 29 ms 4616 KB Output is correct
4 Correct 51 ms 7696 KB Output is correct
5 Correct 39 ms 6092 KB Output is correct
6 Correct 17 ms 2072 KB Output is correct
7 Correct 16 ms 2076 KB Output is correct
8 Correct 14 ms 1384 KB Output is correct
9 Correct 15 ms 1280 KB Output is correct
10 Correct 15 ms 1496 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1178 ms 9488 KB Output is correct
2 Correct 1073 ms 12928 KB Output is correct
3 Correct 670 ms 10236 KB Output is correct
4 Correct 658 ms 9804 KB Output is correct
5 Correct 665 ms 15972 KB Output is correct
6 Correct 659 ms 10136 KB Output is correct
7 Correct 653 ms 9972 KB Output is correct
8 Correct 657 ms 9648 KB Output is correct
9 Correct 665 ms 10168 KB Output is correct
10 Correct 664 ms 9952 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1472 KB Output is correct
2 Correct 19 ms 1536 KB Output is correct
3 Correct 29 ms 4616 KB Output is correct
4 Correct 51 ms 7696 KB Output is correct
5 Correct 39 ms 6092 KB Output is correct
6 Correct 17 ms 2072 KB Output is correct
7 Correct 16 ms 2076 KB Output is correct
8 Correct 14 ms 1384 KB Output is correct
9 Correct 15 ms 1280 KB Output is correct
10 Correct 15 ms 1496 KB Output is correct
11 Correct 1178 ms 9488 KB Output is correct
12 Correct 1073 ms 12928 KB Output is correct
13 Correct 670 ms 10236 KB Output is correct
14 Correct 658 ms 9804 KB Output is correct
15 Correct 665 ms 15972 KB Output is correct
16 Correct 659 ms 10136 KB Output is correct
17 Correct 653 ms 9972 KB Output is correct
18 Correct 657 ms 9648 KB Output is correct
19 Correct 665 ms 10168 KB Output is correct
20 Correct 664 ms 9952 KB Output is correct
21 Correct 1129 ms 9744 KB Output is correct
22 Correct 1018 ms 13124 KB Output is correct
23 Correct 1127 ms 44796 KB Output is correct
24 Correct 1004 ms 77172 KB Output is correct
25 Correct 729 ms 19564 KB Output is correct
26 Correct 694 ms 20104 KB Output is correct
27 Correct 665 ms 16940 KB Output is correct
28 Correct 670 ms 16940 KB Output is correct
29 Correct 1842 ms 19704 KB Output is correct
30 Correct 710 ms 19176 KB Output is correct
31 Correct 693 ms 19296 KB Output is correct
32 Correct 718 ms 20244 KB Output is correct
33 Correct 910 ms 49600 KB Output is correct
34 Correct 694 ms 19032 KB Output is correct
35 Correct 690 ms 19464 KB Output is correct
36 Correct 694 ms 20004 KB Output is correct
37 Correct 704 ms 19788 KB Output is correct
38 Correct 973 ms 48320 KB Output is correct
39 Correct 961 ms 52276 KB Output is correct
40 Correct 916 ms 51420 KB Output is correct
41 Correct 1405 ms 20088 KB Output is correct
42 Correct 1112 ms 21120 KB Output is correct
43 Correct 1033 ms 22744 KB Output is correct
44 Correct 1472 ms 13248 KB Output is correct
45 Correct 1049 ms 13136 KB Output is correct
46 Correct 940 ms 13060 KB Output is correct
47 Correct 684 ms 13968 KB Output is correct
48 Correct 686 ms 14136 KB Output is correct
49 Correct 673 ms 14048 KB Output is correct