Submission #379795

#TimeUsernameProblemLanguageResultExecution timeMemory
379795pit4hDragon 2 (JOI17_dragon2)C++14
0 / 100
43 ms4764 KiB
#include<bits/stdc++.h> #define st first #define nd second #define mp make_pair using namespace std; using ll = long long; using pii = pair<int, int>; const int MAXN = 3e4+1, MAXQ = 1e5+1; int n, m, t[MAXN], q, ans[MAXQ]; int sgn(ll x) { return (x>=0)?x? 1: 0: -1; } struct Point { int x, y; int id; Point() {} Point(int _x, int _y): x(_x), y(_y) {} void read() { cin>>x>>y; } Point operator-(const Point& o) const { return Point(x-o.x, y-o.y); } bool operator<(const Point& o) const { return make_pair(x, y) < make_pair(o.x, o.y); } ll cross(const Point& o) { return (ll)x*o.y - (ll)y*o.x; } ll cross(const Point& o1, const Point& o2) { return (o1 - *this).cross(o2 - *this); } }; Point O1, O2; bool cmp(Point p1, Point p2) { // clockwise if(sgn(O1.cross(O2, p1)) != sgn(O1.cross(O2, p2))) { return (O1.cross(O2, p1) < 0LL)? true : false; } return O1.cross(p1, p2) < 0LL; } Point p[MAXN], pp[MAXN], s[MAXN]; vector<int> tribe[MAXN]; vector<pair<Point, int>> queries[MAXN]; int bit[MAXN]; void add(int idx, int delta) { assert(idx >= 0); for(; idx < n; idx = idx | (idx+1)) { bit[idx] += delta; } } int sum(int r) { assert(r >= 0); int res = 0; for(; r>=0; r = (r & (r+1)) - 1) { res += bit[r]; } return res; } int sum(int l, int r) { return sum(r) - ((l>0)?sum(l-1): 0); } void solve(vector<Point> pts, vector<pair<Point, int>> qs) { sort(pts.begin(), pts.end()); sort(qs.begin(), qs.end()); int j = 0; for(int i=0; i<(int)pts.size(); ++i) { while(j < (int)qs.size() && qs[j].st < pts[i]) { ans[qs[j].nd] += sum(0, qs[j].st.y-1); j++; } add(pts[i].y-1, 1); } while(j < (int)qs.size()) { ans[qs[j].nd] += sum(0, qs[j].st.y-1); j++; } for(int i=0; i<(int)pts.size(); ++i) { add(pts[i].y-1, -1); } } Point reflect(Point pt, Point o) { int dx = o.x - pt.x, dy = o.y - pt.y; pt.x += 2*dx, pt.y += 2*dy; return pt; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1; i<=n; ++i) { p[i].read(); p[i].id = i; cin>>t[i]; tribe[t[i]].push_back(i); } Point P1, P2; P1.read(), P2.read(); if(P2 < P1) swap(P1, P2); for(int i=1; i<=n; ++i) { if(P1.cross(P2, p[i]) > 0LL) { pp[i] = reflect(p[i], P1); } else { pp[i] = p[i]; } } O1 = P1, O2 = P2; sort(pp+1, pp+n+1, cmp); for(int i=1; i<=n; ++i) { s[pp[i].id].x = i; } for(int i=1; i<=n; ++i) { if(P2.cross(P1, p[i]) < 0LL) { pp[i] = reflect(p[i], P2); } else { pp[i] = p[i]; } } O1 = P2, O2 = P1; sort(pp+1, pp+n+1, cmp); for(int i=1; i<=n; ++i) { s[pp[i].id].y = i; } cin>>q; for(int i=1; i<=q; ++i) { int a, b; cin>>a>>b; if(tribe[a].size() > tribe[b].size()) { for(auto j: tribe[b]) { queries[b].push_back(mp(s[j], -i)); } } else { for(auto j: tribe[a]) { queries[b].push_back(mp(s[j], i)); } } } for(int i=1; i<=m; ++i) { vector<Point> up, down, up_r, down_r; vector<pair<Point, int>> upq, downq, upq_r, downq_r; for(auto j: tribe[i]) { if(P1.cross(P2, p[j]) < 0LL) { down.push_back(Point(s[j].x, n-s[j].y+1)); down_r.push_back(Point(n-s[j].x+1, s[j].y)); } else { up.push_back(Point(n-s[j].x+1, s[j].y)); up_r.push_back(Point(s[j].x, n-s[j].y+1)); } } for(auto j: queries[i]) { if(j.nd > 0) { upq.push_back(mp(Point(n-j.st.x+1, j.st.y), j.nd)); downq.push_back(mp(Point(j.st.x, n-j.st.y+1), j.nd)); } else { if(P1.cross(P2, j.st) > 0LL) { upq_r.push_back(mp(Point(j.st.x, n-j.st.y+1), -j.nd)); downq.push_back(mp(Point(j.st.x, n-j.st.y+1), -j.nd)); } else { upq.push_back(mp(Point(n-j.st.x+1, j.st.y), -j.nd)); downq_r.push_back(mp(Point(n-j.st.x+1, j.st.y), -j.nd)); } } } solve(up, upq); solve(down, downq); solve(up_r, upq_r); solve(down_r, downq_r); } for(int i=1; i<=q; ++i) { cout<<ans[i]<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...