Submission #879710

#	Time	Username	Problem	Language	Result	Execution time	Memory
879710		MilosMilutinovic	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	1842 ms	77172 KiB

dragon2

#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 (stderr)

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 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40