Submission #1240320

#TimeUsernameProblemLanguageResultExecution timeMemory
1240320PenguinsAreCuteDragon 2 (JOI17_dragon2)C++17
60 / 100
4086 ms4080 KiB
#include <bits/stdc++.h> using namespace std; using ld = long double; using ll = long long; using cp = complex<long double>; ld PI = arg(-1); struct slope { int x, y; slope(int _x, int _y): x(_x), y(_y) {} slope operator - () {return slope(-x,-y);} }; struct fenwick { int n; vector<int> fw; fenwick(int _n): n(_n+1), fw(_n+1,0) {} void up(int x, int u) { for(x++;x<n;x+=(x&(-x))) fw[x] += u; } int qry(int x) { int ans = 0; for(x++;x;x-=(x&(-x))) ans += fw[x]; return ans; } }; /* Seriously? O(cbrt(N^4 * Q * log^2 N))??? */ const int K = 400; int main() { int n, m; cin >> n >> m; vector<pair<int,int>> dragon[m]; for(int i=0;i<n;i++) { int a, b, c; cin >> a >> b >> c; dragon[c-1].push_back({a,b}); } int d1, e1, d2, e2; cin >> d1 >> e1 >> d2 >> e2; int q; cin >> q; for(int f,g;q--;) { cin >> f >> g; f--; g--; vector<tuple<slope,slope,int>> help; vector<slope> disc; auto cmp0 = [](slope a, slope b) { return (1LL * a.y * b.x < 1LL * a.x * b.y); }; auto cmp1 = [&cmp0,d1,e1,d2,e2](slope x, slope y) { slope z(d2 - d1, e2 - e1); if(cmp0(x,z) == cmp0(y,z)) return cmp0(x,y); return cmp0(x,z); }; auto cmp2 = [&cmp0,d1,e1,d2,e2](slope x, slope y) { slope z(d1 - d2, e1 - e2); if(cmp0(x,z) == cmp0(y,z)) return cmp0(x,y); return cmp0(x,z); }; for(auto [x, y]: dragon[g]) help.push_back({slope(x-d1,y-e1), slope(x-d2,y-e2), 0}); for(auto [x, y]: dragon[f]) { slope fi = slope(x-d1,y-e1); if(cmp1(-fi,fi)) fi = -fi; slope se = slope(x-d2,y-e2); if(cmp2(-se,se)) se = -se; help.push_back({fi, se, 1}); help.push_back({fi, -se, -1}); help.push_back({-fi, se, -1}); help.push_back({-fi, -se, 1}); disc.push_back(se); disc.push_back(-se); } fenwick fw(disc.size()); sort(help.begin(),help.end(), [&cmp1](auto a, auto b) {return cmp1(get<0>(a),get<0>(b));}); sort(disc.begin(),disc.end(), cmp2); int ans = 0; for(auto [fi, se, tp]: help) { int seNw = lower_bound(disc.begin(),disc.end(),se,cmp2) - disc.begin(); if(tp == 0) fw.up(seNw, 1); else ans += tp * fw.qry(seNw); } cout << ans << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...