/*
.:*+=%@@@@@@=-.
.:=@#@@@#@@#######%==*.
.-=####@######%*-.....:%##%.
.*@###########%+:--........-%@-
.*@##############@+--.........-:%-
.+##################@==%%%%=+*:----+.
.-@####################%++%@@@@@=+**%@@*
.%###################@%%@@@###@%+:--%@@%.
-@###################@%%%%*::*%++:-----=@+.
-#####################@%=++++++*:-------.-=:
.+####################@%++*::-:::--::*:::***=:
.@#####################%=++*::::-:::++*=##@@#@-
..#####################@%%=++**:::::**+%@#@%%##-..
.%####################@@%=+++*+****::*=@######@.
.=######################@%%==+==++**+=@%@##@###+:...
-#######################@@@%%%===++=@@@%=++===*::--...
-########################@@@@@@@%==%%=++==@@:::::*:--.
..:#########################@@@@@@%%======++++::-..:-.--...
%#############################@###@%%@@%==%=%*----.--.::---.
#############################################*-:*:-:---*---- .
#############################################*--*--:---*---:-.
#############################################+--::--::-*::-::.
###########################################+:*-.---.---.:---*-..
###########################################**:-----------------.
##########################################@::**:--::::::--:::::-
###########################################:--:*:::::::::**::*+*
###########################################=:::***::::::**:::*+*
############################@@@@@@#########@+****::::********+++
############################@%%%%%@@@@@@@###%+***::::::::***+==+
############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+
#############################@%%%%%%%%%%@#####=::--------:*=%@%+
%###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%=
----------------------------------------------
--------------------------------------------
----------------------------------------------
--------------------------------------------
----------------------------------------------
o###########oo
o##" ""##o
o#" "##
o#" "#o
#" ## ## "##
#" ##
# ################### #
# #
# #
# #
# #
# #
# #
#o #
"#o ##
"#o ##
"#o o#"
"#o ##
"#o o#"
"#ooo ooo#######oo
############### "######o
o###"" "###o # ###
o###o oooo ### oo####"
o###**# #**# ############"
""##""""""""""########### #
# oooooooo#"#** ## #
# # # # ** ## #
#o# #o# *****###ooo#
##
## o###o
## o##***##
o########## #***#**##o
o##" ""### #***##***#
o#######o ### oo#### ##**####*#
o##" ""#############"" ##****###
##" ## ##*##*###
## ### ##### ##
## ### # ## #
## ## #
## ##
## ###
## ###oo
### ""###
###
###
*/
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
ll sqr(ll x){
return x * x;
}
int mysqrt(ll x){
int l = 0, r = 1e9 + 1;
while (r - l > 1){
int m = (l + r) / 2;
if (m * (ll)m <= x)
l = m;
else
r = m;
}
return l;
}
mt19937 rnd(1227);
mt19937_64 rndll(12365);
ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993;
ll myrand(){
ll ZR = (XR * AR + YR * BR + CR) % MODR;
XR = YR;
YR = ZR;
return ZR;
}
const int Mod = 1e9 + 7;
int bpow(int x, int y){
if (y == 0)
return 1;
if (y == 1)
return x;
int ret = bpow(x, y >> 1);
ret = (ret * (ll)ret) % Mod;
if (y & 1)
ret = (ret * (ll)x) % Mod;
return ret;
}
int bdiv(int x, int y){
return (x * (ll)bpow(y, Mod - 2)) % Mod;
}
void setmin(int &x, int y){
x = min(x, y);
}
void setmax(int &x, int y){
x = max(x, y);
}
void setmin(ll &x, ll y){
x = min(x, y);
}
void setmax(ll &x, ll y){
x = max(x, y);
}
int gcd(int a, int b){
return a ? gcd(b % a, a) : b;
}
const ll llinf = 2e18 + 100;
const double eps = 1e-9;
const int maxn = 3e4 + 10, maxw = 1e5 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 16;
struct fenwick{
vector<int> q;
void resz(int n){
q.resize(n, 0);
}
void inc(int i, int v){
for (; i < q.size(); i = (i | (i + 1)))
q[i] += v;
}
int get(int i){
int r = 0;
for (; i >= 0; i = (i & (i + 1)) - 1)
r += q[i];
return r;
}
};
pair<int, int> dif(pair<int, int> x, pair<int, int> y){
return make_pair(y.first - x.first, y.second - x.second);
}
ll cp(pair<int, int> x, pair<int, int> y){
return x.first * (ll)y.second - x.second * (ll)y.first;
}
ll cp(pair<int, int> a, pair<int, int> b, pair<int, int> c){
return cp(dif(a, b), dif(a, c));
}
int quar(pair<int, int> x){
return x.second >= 0;
}
int n, groups;
int zap;
int group[maxn];
pair<int, int> pt[maxn];
pair<int, int> segment[2];
int srt[2][2 * maxn];
int pos[maxn];
int ups[maxn];
vector<pair<pair<int, int>, int> > que[maxn];
int pos1[maxn];
int answer[maxw];
fenwick q[maxn][2];
vector<int> arr[maxn][2];
int siz[maxn][2];
int get(int i, int j, int l, int r, int t){
if (l > r)
return 0;
int w = q[i][j].get(r) - q[i][j].get(l - 1);
if (t == 0)
w = r - l + 1 - w;
return w;
}
void add(int i, int v){
q[group[i]][ups[i]].inc(pos[i], v);
q[group[i]][ups[i]].inc(pos[i] + siz[group[i]][ups[i]], v);
}
void solve(){
int last = 0;
for (int iter = 0; iter < n; iter++){
if (iter > 0)
add(srt[0][iter - 1], -1);
int i = srt[0][iter];
while (last - iter < n && cp(segment[0], pt[i], pt[srt[0][last]]) >= 0)
add(srt[0][last++], 1);
for (auto its : que[group[i]]){
int gr = its.first.first, tp = its.first.second, ansi = its.second;
for (int t = 0; t < 2; t++){
if (arr[gr][t].empty())
continue;
int l, r;
l = -1, r = siz[gr][t];
while (r - l > 1){
int m = (l + r) / 2;
if (pos1[arr[gr][t][m]] > pos1[i])
r = m;
else
l = m;
}
int le, re;
if (r == siz[gr][t])
r = 0;
le = r;
if (cp(segment[1], pt[i], pt[arr[gr][t][r]]) < 0)
re = le - 1;
else{
l = r, r = l + siz[gr][t];
while (r - l > 1){
int m = (l + r) / 2;
if (cp(segment[1], pt[i], pt[arr[gr][t][m]]) > 0)
l = m;
else
r = m;
}
re = l;
}
if (tp == 0){
if (cp(segment[0], pt[i], segment[1]) > 0)
answer[ansi] += get(gr, t, 0, siz[gr][t] - 1, 1) - get(gr, t, le, re, 1);
else
answer[ansi] += get(gr, t, le, re, 0);
}
else{
if (ups[i] != t)
if (cp(segment[0], pt[i], segment[1]) > 0)
answer[ansi] += get(gr, t, 0, siz[gr][t] - 1, 1) - get(gr, t, le, re, 1);
else
answer[ansi] += get(gr, t, le, re, 0);
else
if (cp(segment[0], pt[i], segment[1]) < 0)
answer[ansi] += get(gr, t, 0, siz[gr][t] - 1, 1) - get(gr, t, le, re, 1);
else
answer[ansi] += get(gr, t, le, re, 0);
}
}
}
}
}
void precalc(){
cin >> n >> groups;
for (int i = 0; i < n; i++){
cin >> pt[i].first >> pt[i].second;
cin >> group[i];
group[i]--;
}
for (int i = 0; i < 2; i++)
cin >> segment[i].first >> segment[i].second;
if (segment[0] > segment[1])
swap(segment[0], segment[1]);
for (int t = 0; t < 2; t++){
iota(srt[t], srt[t] + n, 0);
sort(srt[t], srt[t] + n, [&](int i, int j){
auto x = dif(segment[t], pt[i]), y = dif(segment[t], pt[j]);
int w = quar(x), h = quar(y);
if (w != h)
return w > h;
return cp(x, y) > 0;
});
for (int i = 0; i < n; i++)
srt[t][i + n] = srt[t][i];
}
for (int i = 0; i < n; i++)
ups[i] = (cp(segment[0], segment[1], pt[i]) > 0);
for (int it = 0; it < n; it++){
int i = srt[1][it];
pos[i] = siz[group[i]][ups[i]]++;
arr[group[i]][ups[i]].push_back(i);
pos1[i] = it;
}
for (int i = 0; i < groups; i++)
for (int j = 0; j < 2; j++){
q[i][j].resz(2 * siz[i][j]);
for (int k = 0; k < siz[i][j]; k++)
arr[i][j].push_back(arr[i][j][k]);
}
cin >> zap;
for (int i = 0; i < zap; i++){
int x, y;
cin >> x >> y;
x--;
y--;
if (arr[x][0].size() + arr[x][1].size() > arr[y][0].size() + arr[y][1].size())
que[y].push_back(make_pair(make_pair(x, 1), i));
else
que[x].push_back(make_pair(make_pair(y, 0), i));
}
}
int main()
{
#ifdef ONPC
//ifstream cin("a.in");
//ofstream cout("a.out");
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#else
//ifstream cin("gymnasts.in");
//ofstream cout("gymnasts.out");
//freopen("sort.in", "r", stdin);
//freopen("sort.out", "w", stdout);
#endif // ONPC
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
precalc();
solve();
for (int i = 0; i < zap; i++)
cout << answer[i] << '\n';
}
Compilation message
dragon2.cpp: In member function 'void fenwick::inc(int, int)':
dragon2.cpp:186:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; i < q.size(); i = (i | (i + 1)))
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4088 KB |
Output is correct |
| 2 |
Correct |
13 ms |
4168 KB |
Output is correct |
| 3 |
Correct |
41 ms |
4284 KB |
Output is correct |
| 4 |
Correct |
63 ms |
6752 KB |
Output is correct |
| 5 |
Correct |
47 ms |
6752 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6752 KB |
Output is correct |
| 7 |
Correct |
8 ms |
6752 KB |
Output is correct |
| 8 |
Correct |
8 ms |
6752 KB |
Output is correct |
| 9 |
Correct |
7 ms |
6752 KB |
Output is correct |
| 10 |
Correct |
7 ms |
6752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
6752 KB |
Output is correct |
| 2 |
Correct |
161 ms |
6752 KB |
Output is correct |
| 3 |
Correct |
57 ms |
6752 KB |
Output is correct |
| 4 |
Correct |
37 ms |
6752 KB |
Output is correct |
| 5 |
Correct |
40 ms |
7148 KB |
Output is correct |
| 6 |
Correct |
37 ms |
7148 KB |
Output is correct |
| 7 |
Correct |
37 ms |
7148 KB |
Output is correct |
| 8 |
Correct |
39 ms |
7148 KB |
Output is correct |
| 9 |
Correct |
33 ms |
7148 KB |
Output is correct |
| 10 |
Correct |
30 ms |
7148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4088 KB |
Output is correct |
| 2 |
Correct |
13 ms |
4168 KB |
Output is correct |
| 3 |
Correct |
41 ms |
4284 KB |
Output is correct |
| 4 |
Correct |
63 ms |
6752 KB |
Output is correct |
| 5 |
Correct |
47 ms |
6752 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6752 KB |
Output is correct |
| 7 |
Correct |
8 ms |
6752 KB |
Output is correct |
| 8 |
Correct |
8 ms |
6752 KB |
Output is correct |
| 9 |
Correct |
7 ms |
6752 KB |
Output is correct |
| 10 |
Correct |
7 ms |
6752 KB |
Output is correct |
| 11 |
Correct |
50 ms |
6752 KB |
Output is correct |
| 12 |
Correct |
161 ms |
6752 KB |
Output is correct |
| 13 |
Correct |
57 ms |
6752 KB |
Output is correct |
| 14 |
Correct |
37 ms |
6752 KB |
Output is correct |
| 15 |
Correct |
40 ms |
7148 KB |
Output is correct |
| 16 |
Correct |
37 ms |
7148 KB |
Output is correct |
| 17 |
Correct |
37 ms |
7148 KB |
Output is correct |
| 18 |
Correct |
39 ms |
7148 KB |
Output is correct |
| 19 |
Correct |
33 ms |
7148 KB |
Output is correct |
| 20 |
Correct |
30 ms |
7148 KB |
Output is correct |
| 21 |
Correct |
58 ms |
7148 KB |
Output is correct |
| 22 |
Correct |
145 ms |
7148 KB |
Output is correct |
| 23 |
Correct |
1104 ms |
7148 KB |
Output is correct |
| 24 |
Correct |
1427 ms |
8732 KB |
Output is correct |
| 25 |
Correct |
120 ms |
9116 KB |
Output is correct |
| 26 |
Correct |
138 ms |
9700 KB |
Output is correct |
| 27 |
Correct |
59 ms |
9700 KB |
Output is correct |
| 28 |
Correct |
44 ms |
9700 KB |
Output is correct |
| 29 |
Correct |
174 ms |
9700 KB |
Output is correct |
| 30 |
Correct |
87 ms |
10924 KB |
Output is correct |
| 31 |
Correct |
87 ms |
12856 KB |
Output is correct |
| 32 |
Correct |
108 ms |
14688 KB |
Output is correct |
| 33 |
Correct |
818 ms |
16336 KB |
Output is correct |
| 34 |
Correct |
85 ms |
18064 KB |
Output is correct |
| 35 |
Correct |
115 ms |
19712 KB |
Output is correct |
| 36 |
Correct |
91 ms |
21616 KB |
Output is correct |
| 37 |
Correct |
133 ms |
23800 KB |
Output is correct |
| 38 |
Correct |
754 ms |
24936 KB |
Output is correct |
| 39 |
Correct |
906 ms |
26696 KB |
Output is correct |
| 40 |
Correct |
869 ms |
28356 KB |
Output is correct |
| 41 |
Correct |
131 ms |
29876 KB |
Output is correct |
| 42 |
Correct |
192 ms |
31508 KB |
Output is correct |
| 43 |
Correct |
204 ms |
33232 KB |
Output is correct |
| 44 |
Correct |
74 ms |
33232 KB |
Output is correct |
| 45 |
Correct |
61 ms |
33232 KB |
Output is correct |
| 46 |
Correct |
58 ms |
33288 KB |
Output is correct |
| 47 |
Correct |
58 ms |
33984 KB |
Output is correct |
| 48 |
Correct |
61 ms |
34936 KB |
Output is correct |
| 49 |
Correct |
60 ms |
35764 KB |
Output is correct |
