| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 595037 |
2022-07-13T09:21:12 Z |
반딧불(#8437) |
Dragon 2 (JOI17_dragon2) |
C++17 |
|
4000 ms |
11036 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Frac{
ll a, b;
Frac(){}
Frac(ll a, ll b): a(a), b(b){
ll g = __gcd(a, b);
a/=g, b/=g;
if(b<0) a=-a, b=-b;
}
bool operator<(const Frac &r)const{
return a*r.b < b*r.a;
}
};
struct vector2{
ll x, y;
vector2(){}
vector2(ll x, ll y): x(x), y(y){}
vector2 operator+(const vector2 &r)const{
return vector2(x+r.x, y+r.y);
}
vector2 operator-(const vector2 &r)const{
return vector2(x-r.x, y-r.y);
}
ll cross(vector2 r)const{
return x*r.y - y*r.x;
}
bool operator<(const vector2 &r)const{
return cross(r) > 0;
}
};
struct Query{
int x, y, idx;
Query(){}
Query(int x, int y, int idx): x(x), y(y), idx(idx){}
bool operator<(const Query &r)const{
return x==r.x ? y<r.y : x<r.x;
}
};
ll ccw(vector2 a, vector2 b){
return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
return (b-a).cross(c-a);
}
inline ll sign(ll x){
return x>0?1:-1;
}
int n, k, q;
vector2 arr[30002];
int group[30002];
ll calc[30002];
vector<int> groupList[30002][2];
vector2 ps, pe;
int ans[100002];
Query query[100002];
void input();
void operate();
int main(){
input();
operate();
}
void input(){
scanf("%d %d", &n, &k);
for(int i=1; i<=n; i++){
scanf("%lld %lld %d", &arr[i].x, &arr[i].y, &group[i]);
}
scanf("%lld %lld %lld %lld %d", &ps.x, &ps.y, &pe.x, &pe.y, &q);
for(int i=1; i<=q; i++){
scanf("%d %d", &query[i].x, &query[i].y);
query[i].idx = i;
}
}
void makePositive(){ /// ps�� 0����, pe�� ������ 0 �̻� 90�� �̸����� ����
for(int i=1; i<=n; i++) arr[i] = arr[i] - ps;
pe = pe - ps, ps = ps - ps;
bool cx = (pe.x < 0), cy = (pe.y < 0);
for(int i=1; i<=n; i++){
if(cx) arr[i].x = -arr[i].x;
if(cy) arr[i].y = -arr[i].y;
}
if(cx) pe.x = -pe.x;
if(cy) pe.y = -pe.y;
if(pe.x==0){
for(int i=1; i<=n; i++) swap(arr[i].x, arr[i].y);
swap(pe.x, pe.y);
}
}
void putIntoGroup(){ /// groupList�� ����ֱ�
for(int i=1; i<=n; i++){
if(ccw(ps, pe, arr[i]) > 0) groupList[group[i]][0].push_back(i);
else groupList[group[i]][1].push_back(i);
}
}
struct dat{
int x, y, w;
dat(){}
dat(int x, int y, int w): x(x), y(y), w(w){}
bool operator<(const dat &r)const{
return x<r.x;
}
};
struct Fenwick{
int n;
int tree[40002];
void init(int _n){
n = _n;
for(int i=0; i<=n; i++) tree[i] = 0;
}
void add(int x, int y){
while(x<=n){
tree[x] += y;
x += x&-x;
}
}
int sum(int x){
int ret = 0;
while(x){
ret += tree[x];
x -= x&-x;
}
return ret;
}
int sum(int l, int r){
return sum(r) - sum(l-1);
}
} tree;
map<pair<int, int>, int> mp;
int processQuery(int gx, int gy){
if(mp.find(make_pair(gx, gy)) != mp.end()) return mp[make_pair(gx, gy)];
int ret = 0;
if(!groupList[gx][0].empty() && !groupList[gy][0].empty()){ /// 00 ó��
vector<vector2> va, vb;
for(int x: groupList[gx][0]) va.push_back(arr[x] - ps), vb.push_back(arr[x] - pe);
for(int x: groupList[gy][0]) va.push_back(arr[x] - ps), vb.push_back(arr[x] - pe);
sort(va.begin(), va.end());
sort(vb.begin(), vb.end());
vector<dat> vec;
for(int x: groupList[gx][0]){
vec.push_back(dat(lower_bound(va.begin(), va.end(), arr[x]-ps) - va.begin() + 1,
lower_bound(vb.begin(), vb.end(), arr[x]-pe) - vb.begin() + 1, 0));
}
for(int x: groupList[gy][0]){
vec.push_back(dat(lower_bound(va.begin(), va.end(), arr[x]-ps) - va.begin() + 1,
lower_bound(vb.begin(), vb.end(), arr[x]-pe) - vb.begin() + 1, 1));
}
sort(vec.begin(), vec.end());
tree.init((int)vec.size());
for(dat tmp: vec){
if(!tmp.w) ret += tree.sum(tmp.y, (int)vec.size());
else tree.add(tmp.y, 1);
}
}
if(!groupList[gx][1].empty() && !groupList[gy][1].empty()){ /// 11 ó��
vector<vector2> va, vb;
for(int x: groupList[gx][1]) va.push_back(arr[x] - ps), vb.push_back(arr[x] - pe);
for(int x: groupList[gy][1]) va.push_back(arr[x] - ps), vb.push_back(arr[x] - pe);
sort(va.begin(), va.end());
sort(vb.begin(), vb.end());
vector<dat> vec;
for(int x: groupList[gx][1]){
vec.push_back(dat(lower_bound(va.begin(), va.end(), arr[x]-ps) - va.begin() + 1,
lower_bound(vb.begin(), vb.end(), arr[x]-pe) - vb.begin() + 1, 0));
}
for(int x: groupList[gy][1]){
vec.push_back(dat(lower_bound(va.begin(), va.end(), arr[x]-ps) - va.begin() + 1,
lower_bound(vb.begin(), vb.end(), arr[x]-pe) - vb.begin() + 1, 1));
}
for(dat &p: vec) swap(p.x, p.y);
sort(vec.begin(), vec.end());
tree.init((int)vec.size());
for(dat tmp: vec){
if(!tmp.w) ret += tree.sum(tmp.y, (int)vec.size());
else tree.add(tmp.y, 1);
}
}
if(!groupList[gx][0].empty() && !groupList[gy][1].empty()){ /// 01 ó��
vector<vector2> psv, pev;
for(int x: groupList[gy][1]) psv.push_back(arr[x] - ps), pev.push_back(arr[x] - pe);
sort(psv.begin(), psv.end()), sort(pev.begin(), pev.end());
for(int x: groupList[gx][0]){
int A = lower_bound(psv.begin(), psv.end(), ps - arr[x]) - psv.begin();
int B = pev.end() - lower_bound(pev.begin(), pev.end(), pe - arr[x]);
ret += (int)psv.size() - A - B;
}
}
if(!groupList[gx][1].empty() && !groupList[gy][0].empty()){ /// 10 ó��
vector<vector2> psv, pev;
for(int x: groupList[gy][0]) psv.push_back(arr[x] - ps), pev.push_back(arr[x] - pe);
sort(psv.begin(), psv.end()), sort(pev.begin(), pev.end());
for(int x: groupList[gx][1]){
int A = psv.end() - lower_bound(psv.begin(), psv.end(), ps - arr[x]);
int B = lower_bound(pev.begin(), pev.end(), pe - arr[x]) - pev.begin();
ret += (int)psv.size() - A - B;
}
}
return mp[make_pair(gx, gy)] = ret;
}
void processQueries(){
for(int i=1; i<=q; i++){
ans[i] = processQuery(query[i].x, query[i].y);
}
}
void operate(){
makePositive();
putIntoGroup();
processQueries();
for(int i=1; i<=q; i++) printf("%d\n", ans[i]);
}
Compilation message
dragon2.cpp: In function 'void input()':
dragon2.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%lld %lld %d", &arr[i].x, &arr[i].y, &group[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%lld %lld %lld %lld %d", &ps.x, &ps.y, &pe.x, &pe.y, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%d %d", &query[i].x, &query[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1952 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1856 KB |
Output is correct |
| 3 |
Correct |
86 ms |
2112 KB |
Output is correct |
| 4 |
Correct |
189 ms |
9740 KB |
Output is correct |
| 5 |
Correct |
120 ms |
9848 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2004 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
3864 KB |
Output is correct |
| 2 |
Correct |
169 ms |
2928 KB |
Output is correct |
| 3 |
Correct |
44 ms |
2512 KB |
Output is correct |
| 4 |
Correct |
14 ms |
2536 KB |
Output is correct |
| 5 |
Correct |
20 ms |
3028 KB |
Output is correct |
| 6 |
Correct |
28 ms |
4156 KB |
Output is correct |
| 7 |
Correct |
27 ms |
4228 KB |
Output is correct |
| 8 |
Correct |
14 ms |
3116 KB |
Output is correct |
| 9 |
Correct |
17 ms |
3420 KB |
Output is correct |
| 10 |
Correct |
11 ms |
3056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1952 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1856 KB |
Output is correct |
| 3 |
Correct |
86 ms |
2112 KB |
Output is correct |
| 4 |
Correct |
189 ms |
9740 KB |
Output is correct |
| 5 |
Correct |
120 ms |
9848 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2004 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 11 |
Correct |
34 ms |
3864 KB |
Output is correct |
| 12 |
Correct |
169 ms |
2928 KB |
Output is correct |
| 13 |
Correct |
44 ms |
2512 KB |
Output is correct |
| 14 |
Correct |
14 ms |
2536 KB |
Output is correct |
| 15 |
Correct |
20 ms |
3028 KB |
Output is correct |
| 16 |
Correct |
28 ms |
4156 KB |
Output is correct |
| 17 |
Correct |
27 ms |
4228 KB |
Output is correct |
| 18 |
Correct |
14 ms |
3116 KB |
Output is correct |
| 19 |
Correct |
17 ms |
3420 KB |
Output is correct |
| 20 |
Correct |
11 ms |
3056 KB |
Output is correct |
| 21 |
Correct |
33 ms |
3848 KB |
Output is correct |
| 22 |
Correct |
175 ms |
2956 KB |
Output is correct |
| 23 |
Correct |
1221 ms |
2832 KB |
Output is correct |
| 24 |
Correct |
1796 ms |
10724 KB |
Output is correct |
| 25 |
Correct |
207 ms |
10768 KB |
Output is correct |
| 26 |
Correct |
114 ms |
11036 KB |
Output is correct |
| 27 |
Correct |
23 ms |
4436 KB |
Output is correct |
| 28 |
Correct |
25 ms |
4472 KB |
Output is correct |
| 29 |
Execution timed out |
4067 ms |
5252 KB |
Time limit exceeded |
| 30 |
Halted |
0 ms |
0 KB |
- |
