Submission #595064

#TimeUsernameProblemLanguageResultExecution timeMemory
595064lohachoDragon 2 (JOI17_dragon2)C++14
60 / 100
4016 ms49088 KiB
#include <bits/stdc++.h> using namespace std; const int NS = 120004, QS = (int)1e5 + 4; int n, m, q, B; pair<int, int> a[NS]; int col[NS]; vector<int> gr[NS]; int ind[NS][2]; pair<int, int> range[NS][2]; pair<int, int> p[2]; int ans[QS]; struct Data{ int l, r, sum, lazy; Data(){} }; int tN, st[NS]; Data tr[NS * 100]; void push(int x, int l, int r, int pl, int pr, int val){ if(pl <= l && pr >= r){ tr[x].sum += val; tr[x].lazy += val; return; } if(tr[x].lazy){ ++tN; tr[tN] = tr[tr[x].l]; tr[tN].sum += tr[x].lazy, tr[tN].lazy += tr[x].lazy; ++tN; tr[tN] = tr[tr[x].r]; tr[tN].sum += tr[x].lazy, tr[tN].lazy += tr[x].lazy; tr[x].l = tN - 1, tr[x].r = tN; tr[x].lazy = 0; } int m = l + r >> 1; if(!(pr < l || pl > m)){ ++tN, tr[tN] = tr[tr[x].l], tr[x].l = tN; push(tr[x].l, l, m, pl, pr, val); } if(!(pr <= m || pl > r)){ ++tN, tr[tN] = tr[tr[x].r], tr[x].r = tN; push(tr[x].r, m + 1, r, pl, pr, val); } tr[x].sum = tr[tr[x].l].sum + tr[tr[x].r].sum; } int get(int pre, int x, int l, int r, int fl, int fr){ if(fl <= l && fr >= r) return tr[x].sum - tr[pre].sum; if(tr[x].lazy){ ++tN; tr[tN] = tr[tr[x].l]; tr[tN].sum += tr[x].lazy, tr[tN].lazy += tr[x].lazy; ++tN; tr[tN] = tr[tr[x].r]; tr[tN].sum += tr[x].lazy, tr[tN].lazy += tr[x].lazy; tr[x].l = tN - 1, tr[x].r = tN; tr[x].lazy = 0; } if(tr[pre].lazy){ ++tN; tr[tN] = tr[tr[pre].l]; tr[tN].sum += tr[pre].lazy, tr[tN].lazy += tr[pre].lazy; ++tN; tr[tN] = tr[tr[pre].r]; tr[tN].sum += tr[pre].lazy, tr[tN].lazy += tr[pre].lazy; tr[pre].l = tN - 1, tr[pre].r = tN; tr[pre].lazy = 0; } int m = l + r >> 1; int rv = 0; if(!(fr < l || fl > m)){ rv += get(tr[pre].l, tr[x].l, l, m, fl, fr); } if(!(fr <= m || fl > r)){ rv += get(tr[pre].r, tr[x].r, m + 1, r, fl, fr); } return rv; } int ccw(pair<int, int> bs, pair<int, int> x, pair<int, int> y){ x.first -= bs.first, x.second -= bs.second; y.first -= bs.first, y.second -= bs.second; long long val = (long long)x.first * y.second - (long long)x.second * y.first; return (val ? val > 0 ? 1 : -1 : 0); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 0; i < n; ++i){ cin >> a[i].first >> a[i].second >> col[i]; --col[i]; gr[col[i]].push_back(i); } cin >> p[0].first >> p[0].second >> p[1].first >> p[1].second; for(int k = 0; k < 2; ++k){ vector<vector<int>> u, d; for(int j = 0; j < n; ++j){ if(a[j].second > p[k].second || (a[j].second == p[k].second && a[j].first < p[k].first)){ u.push_back({a[j].first, a[j].second, j}); } else{ d.push_back({a[j].first, a[j].second, j}); } } auto comp = [&](vector<int>&x, vector<int>&y){return ccw(p[k], {x[0], x[1]}, {y[0], y[1]}) < 0;}; sort(u.begin(), u.end(), comp), sort(d.begin(), d.end(), comp); for(auto&i:d){ u.push_back(i); } int r = 0, ldir = 0; for(int l = 0; l < (int)u.size(); ++l){ int dir = ((k == 0) ^ (ccw({u[l][0], u[l][1]}, p[0], p[1]) == -1)); dir = (dir ? 1 : -1); if(ldir && dir != ldir){ r = l; } ldir = dir; while(true){ int ca = ccw(p[k], {u[l][0], u[l][1]}, {u[r][0], u[r][1]}); int cb = ccw(p[k], {u[l][0], u[l][1]}, p[1 - k]); if(ca == cb || !ca || !cb) break; r = (r - dir + (int)u.size()) % (int)u.size(); } while(true){ int nr = (r + dir + (int)u.size()) % (int)u.size(); int ca = ccw(p[k], {u[l][0], u[l][1]}, {u[nr][0], u[nr][1]}); int cb = ccw(p[k], {u[l][0], u[l][1]}, p[1 - k]); if(ca != cb) break; r = nr; } ind[u[l][2]][k] = l; if(ccw(p[k], {u[l][0], u[l][1]}, {u[r][0], u[r][1]}) == -1){ range[u[l][2]][k] = {l, r + (r < l ? n : 0)}; } else{ range[u[l][2]][k] = {r, l + (l < r ? n : 0)}; } } } B = 150; vector<vector<int>> q1, q2, q3; cin >> q; for(int i = 0; i < q; ++i){ int x, y; cin >> x >> y; --x, --y; if((int)gr[x].size() < B && (int)gr[y].size() < B){ q1.push_back({x, y, i}); } else if((int)gr[x].size() < B){ q2.push_back({x, y, i}); } else{ q3.push_back({x, y, i}); } } for(auto&rep:q1){ int x = rep[0], y = rep[1], id = rep[2]; int dap = 0; for(int i = 0; i < (int)gr[x].size(); ++i){ for(int j = 0; j < (int)gr[y].size(); ++j){ if(ind[gr[y][j]][0] >= range[gr[x][i]][0].first && ind[gr[y][j]][0] <= range[gr[x][i]][0].second){ if(ind[gr[y][j]][1] >= range[gr[x][i]][1].first && ind[gr[y][j]][1] <= range[gr[x][i]][1].second) ++dap; } if(ind[gr[y][j]][0] + n >= range[gr[x][i]][0].first && ind[gr[y][j]][0] + n <= range[gr[x][i]][0].second){ if(ind[gr[y][j]][1] >= range[gr[x][i]][1].first && ind[gr[y][j]][1] <= range[gr[x][i]][1].second) ++dap; } if(ind[gr[y][j]][0] >= range[gr[x][i]][0].first && ind[gr[y][j]][0] <= range[gr[x][i]][0].second){ if(ind[gr[y][j]][1] + n >= range[gr[x][i]][1].first && ind[gr[y][j]][1] + n <= range[gr[x][i]][1].second) ++dap; } if(ind[gr[y][j]][0] + n >= range[gr[x][i]][0].first && ind[gr[y][j]][0] + n <= range[gr[x][i]][0].second){ if(ind[gr[y][j]][1] + n >= range[gr[x][i]][1].first && ind[gr[y][j]][1] + n <= range[gr[x][i]][1].second) ++dap; } } } vector<pair<int, int>> srt; for(int j = 0; j < (int)gr[y].size(); ++j){ srt.push_back({ind[gr[y][j]][0], ind[gr[y][j]][1]}); srt.push_back({ind[gr[y][j]][0], ind[gr[y][j]][1] + n}); srt.push_back({ind[gr[y][j]][0] + n, ind[gr[y][j]][1]}); srt.push_back({ind[gr[y][j]][0] + n, ind[gr[y][j]][1] + n}); } sort(srt.begin(), srt.end()); tN = 0; for(int i = 0; i < (int)srt.size(); ++i){ st[i] = ++tN; tr[tN] = tr[i ? st[i - 1] : 0]; push(st[i], 0, 2 * n - 1, srt[i].second, srt[i].second, 1); } int nans = 0; for(int i = 0; i < (int)gr[x].size(); ++i){ int p2 = lower_bound(srt.begin(), srt.end(), make_pair(range[gr[x][i]][0].second + 1, -(int)1e9)) - srt.begin() - 1; int p1 = lower_bound(srt.begin(), srt.end(), make_pair(range[gr[x][i]][0].first, -(int)1e9)) - srt.begin(); nans += get(p1 > 0 ? st[p1 - 1] : 0, st[p2], 0, 2 * n - 1, range[gr[x][i]][1].first, range[gr[x][i]][1].second); } ans[id] = nans; } sort(q2.begin(), q2.end(), [&](vector<int>&x, vector<int>&y){return x[1] < y[1];}); vector<pair<int, int>> srt; for(int i = 0; i < (int)q2.size(); ++i){ int x = q2[i][0], y = q2[i][1], id = q2[i][2]; if(!i || y != q2[i - 1][1]){ srt.clear(); for(int j = 0; j < (int)gr[y].size(); ++j){ srt.push_back({ind[gr[y][j]][0], ind[gr[y][j]][1]}); srt.push_back({ind[gr[y][j]][0], ind[gr[y][j]][1] + n}); srt.push_back({ind[gr[y][j]][0] + n, ind[gr[y][j]][1]}); srt.push_back({ind[gr[y][j]][0] + n, ind[gr[y][j]][1] + n}); } sort(srt.begin(), srt.end()); tN = 0; for(int k = 0; k < (int)srt.size(); ++k){ st[k] = ++tN; tr[tN] = tr[k ? st[k - 1] : 0]; push(st[k], 0, 2 * n - 1, srt[k].second, srt[k].second, 1); } } int nans = 0; for(int j = 0; j < (int)gr[x].size(); ++j){ int p2 = lower_bound(srt.begin(), srt.end(), make_pair(range[gr[x][j]][0].second + 1, -(int)1e9)) - srt.begin() - 1; int p1 = lower_bound(srt.begin(), srt.end(), make_pair(range[gr[x][j]][0].first, -(int)1e9)) - srt.begin(); nans += get(p1 > 0 ? st[p1 - 1] : 0, st[p2], 0, 2 * n - 1, range[gr[x][j]][1].first, range[gr[x][j]][1].second); } ans[id] = nans; } sort(q3.begin(), q3.end(), [&](vector<int>&x, vector<int>&y){return x[0] < y[0];}); vector<vector<int>> srt2; for(int i = 0; i < (int)q3.size(); ++i){ int x = q3[i][0], y = q3[i][1], id = q3[i][2]; if(!i || x != q3[i - 1][0]){ srt2.clear(); for(int j = 0; j < (int)gr[x].size(); ++j){ srt2.push_back({range[gr[x][j]][0].first, range[gr[x][j]][1].first, range[gr[x][j]][1].second, 1}); srt2.push_back({range[gr[x][j]][0].second + 1, range[gr[x][j]][1].first, range[gr[x][j]][1].second, -1}); } sort(srt2.begin(), srt2.end()); tN = 0; for(int k = 0; k < (int)srt2.size(); ++k){ st[k] = ++tN; tr[tN] = tr[k ? st[k - 1] : 0]; push(st[k], 0, 2 * n - 1, srt2[k][1], srt2[k][2], srt2[k][3]); } } int nans = 0; for(int j = 0; j < (int)gr[y].size(); ++j){ int fx = ind[gr[y][j]][0], fy = ind[gr[y][j]][1]; int p2 = lower_bound(srt2.begin(), srt2.end(), vector<int>{fx + 1, -(int)1e9, 0, 0}) - srt2.begin() - 1; nans += get(0, st[p2], 0, 2 * n - 1, fy, fy); fy += n; p2 = lower_bound(srt2.begin(), srt2.end(), vector<int>{fx + 1, -(int)1e9, 0, 0}) - srt2.begin() - 1; nans += get(0, st[p2], 0, 2 * n - 1, fy, fy); fx += n; p2 = lower_bound(srt2.begin(), srt2.end(), vector<int>{fx + 1, -(int)1e9, 0, 0}) - srt2.begin() - 1; nans += get(0, st[p2], 0, 2 * n - 1, fy, fy); fy -= n; p2 = lower_bound(srt2.begin(), srt2.end(), vector<int>{fx + 1, -(int)1e9, 0, 0}) - srt2.begin() - 1; nans += get(0, st[p2], 0, 2 * n - 1, fy, fy); } ans[id] = nans; } for(int i = 0; i < q; ++i){ cout << ans[i] << '\n'; } return 0; }

Compilation message (stderr)

dragon2.cpp: In function 'void push(int, int, int, int, int, int)':
dragon2.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m = l + r >> 1;
      |             ~~^~~
dragon2.cpp: In function 'int get(int, int, int, int, int, int)':
dragon2.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int m = l + r >> 1;
      |             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...