| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 818368 |
2023-08-10T04:31:44 Z |
이동현(#10134) |
Dragon 2 (JOI17_dragon2) |
C++17 |
|
3537 ms |
49948 KB |
#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 = 100;
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
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 time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6520 KB |
Output is correct |
| 2 |
Correct |
19 ms |
4624 KB |
Output is correct |
| 3 |
Correct |
125 ms |
3808 KB |
Output is correct |
| 4 |
Correct |
246 ms |
10136 KB |
Output is correct |
| 5 |
Correct |
105 ms |
10300 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3664 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3664 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5600 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4572 KB |
Output is correct |
| 10 |
Correct |
5 ms |
4460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
43232 KB |
Output is correct |
| 2 |
Correct |
208 ms |
18920 KB |
Output is correct |
| 3 |
Correct |
76 ms |
7748 KB |
Output is correct |
| 4 |
Correct |
27 ms |
7748 KB |
Output is correct |
| 5 |
Correct |
29 ms |
8620 KB |
Output is correct |
| 6 |
Correct |
48 ms |
19092 KB |
Output is correct |
| 7 |
Correct |
60 ms |
19732 KB |
Output is correct |
| 8 |
Correct |
54 ms |
29004 KB |
Output is correct |
| 9 |
Correct |
37 ms |
19168 KB |
Output is correct |
| 10 |
Correct |
38 ms |
18876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6520 KB |
Output is correct |
| 2 |
Correct |
19 ms |
4624 KB |
Output is correct |
| 3 |
Correct |
125 ms |
3808 KB |
Output is correct |
| 4 |
Correct |
246 ms |
10136 KB |
Output is correct |
| 5 |
Correct |
105 ms |
10300 KB |
Output is correct |
| 6 |
Correct |
5 ms |
3664 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3664 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5600 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4572 KB |
Output is correct |
| 10 |
Correct |
5 ms |
4460 KB |
Output is correct |
| 11 |
Correct |
78 ms |
43232 KB |
Output is correct |
| 12 |
Correct |
208 ms |
18920 KB |
Output is correct |
| 13 |
Correct |
76 ms |
7748 KB |
Output is correct |
| 14 |
Correct |
27 ms |
7748 KB |
Output is correct |
| 15 |
Correct |
29 ms |
8620 KB |
Output is correct |
| 16 |
Correct |
48 ms |
19092 KB |
Output is correct |
| 17 |
Correct |
60 ms |
19732 KB |
Output is correct |
| 18 |
Correct |
54 ms |
29004 KB |
Output is correct |
| 19 |
Correct |
37 ms |
19168 KB |
Output is correct |
| 20 |
Correct |
38 ms |
18876 KB |
Output is correct |
| 21 |
Correct |
82 ms |
43040 KB |
Output is correct |
| 22 |
Correct |
264 ms |
19016 KB |
Output is correct |
| 23 |
Correct |
1193 ms |
13820 KB |
Output is correct |
| 24 |
Correct |
3061 ms |
12232 KB |
Output is correct |
| 25 |
Correct |
339 ms |
12300 KB |
Output is correct |
| 26 |
Correct |
141 ms |
12728 KB |
Output is correct |
| 27 |
Correct |
34 ms |
8268 KB |
Output is correct |
| 28 |
Correct |
34 ms |
8260 KB |
Output is correct |
| 29 |
Correct |
172 ms |
49948 KB |
Output is correct |
| 30 |
Correct |
134 ms |
41612 KB |
Output is correct |
| 31 |
Correct |
143 ms |
49484 KB |
Output is correct |
| 32 |
Correct |
1658 ms |
12756 KB |
Output is correct |
| 33 |
Correct |
3457 ms |
14692 KB |
Output is correct |
| 34 |
Correct |
140 ms |
12740 KB |
Output is correct |
| 35 |
Correct |
125 ms |
12528 KB |
Output is correct |
| 36 |
Correct |
145 ms |
12504 KB |
Output is correct |
| 37 |
Correct |
155 ms |
12780 KB |
Output is correct |
| 38 |
Correct |
1078 ms |
16384 KB |
Output is correct |
| 39 |
Correct |
2285 ms |
16264 KB |
Output is correct |
| 40 |
Correct |
3537 ms |
15088 KB |
Output is correct |
| 41 |
Correct |
157 ms |
35396 KB |
Output is correct |
| 42 |
Correct |
185 ms |
25076 KB |
Output is correct |
| 43 |
Correct |
244 ms |
21828 KB |
Output is correct |
| 44 |
Correct |
86 ms |
44928 KB |
Output is correct |
| 45 |
Correct |
73 ms |
27444 KB |
Output is correct |
| 46 |
Correct |
72 ms |
20196 KB |
Output is correct |
| 47 |
Correct |
64 ms |
23568 KB |
Output is correct |
| 48 |
Correct |
52 ms |
15128 KB |
Output is correct |
| 49 |
Correct |
47 ms |
13320 KB |
Output is correct |
