| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 819181 |
2023-08-10T08:20:29 Z |
반딧불(#10131) |
Dragon 2 (JOI17_dragon2) |
C++17 |
|
4000 ms |
5844 KB |
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
void input();
void init();
void solve();
void output();
int main(){
input();
init();
solve();
output();
}
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;
}
};
ll ccw(vector2 a, vector2 b){
return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
return (b-a).cross(c-a);
}
int n, m, q;
int tribe[3002];
vector2 point[30002], la, lb;
vector<int> tribeVec[30002];
int qx[100002], qy[100002];
void input(){
scanf("%d %d", &n, &m);
for(int i=1; i<=n; i++){
scanf("%lld %lld %d", &point[i].x, &point[i].y, &tribe[i]);
tribeVec[tribe[i]].push_back(i);
}
scanf("%lld %lld %lld %lld", &la.x, &la.y, &lb.x, &lb.y);
scanf("%d", &q);
for(int i=1; i<=q; i++){
scanf("%d %d", &qx[i], &qy[i]);
}
}
vector2 pointA[30002], pointB[30002]; bool type[30002];
vector<int> tribeGroupA[30002][2], tribeGroupB[30002][2];
int idxA[30002], idxB[30002], tribeCnt[30002];
void init(){
for(int i=1; i<=n; i++){
tribeCnt[tribe[i]]++;
pointA[i] = point[i] - la, pointB[i] = point[i] - lb;
if(ccw(la, lb, point[i]) > 0) type[i] = 0;
else type[i] = 1;
tribeGroupA[tribe[i]][type[i]].push_back(i);
tribeGroupB[tribe[i]][type[i]].push_back(i);
}
for(int i=1; i<=m; i++){
for(int t=0; t<2; t++){
sort(tribeGroupA[i][t].begin(), tribeGroupA[i][t].end(), [&](int x, int y){
return ccw(pointA[x], pointA[y]) < 0;
});
for(int j=0; j<(int)tribeGroupA[i][t].size(); j++) idxA[tribeGroupA[i][t][j]] = j;
sort(tribeGroupB[i][t].begin(), tribeGroupB[i][t].end(), [&](int x, int y){
return ccw(pointB[x], pointB[y]) < 0;
});
for(int j=0; j<(int)tribeGroupB[i][t].size(); j++) idxB[tribeGroupB[i][t][j]] = j;
}
}
}
struct Fenwick{
int n;
int tree[30002];
void init(int _n){
n = _n;
for(int i=1; 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>0){
ret += tree[x];
x-=x&-x;
}
return ret;
}
int sum(int l, int r){
if(l>r) return 0;
return sum(r) - sum(l-1);
}
} fenwick;
int ans[100002];
void addAns(int s, int e, int q){
/// [s][0] -> [e][1]로 가는 것들만을 센다.
int ret = 0, sz = (int)tribeGroupA[e][1].size();
for(int x: tribeGroupA[s][0]){
ret += sz;
ret -= sz - (upper_bound(tribeGroupA[e][1].begin(), tribeGroupA[e][1].end(), x, [&](int A, int B){
return ccw(pointA[A], pointA[B]) > 0;
}) - tribeGroupA[e][1].begin());
ret -= upper_bound(tribeGroupB[e][1].begin(), tribeGroupB[e][1].end(), x, [&](int A, int B){
return ccw(pointB[A], pointB[B]) > 0;
}) - tribeGroupB[e][1].begin();
}
ans[q] += ret;
}
struct Query{
int x, yl, yr, v, q;
Query(){}
Query(int x, int yl, int yr, int v, int q): x(x), yl(yl), yr(yr), v(v), q(q){}
bool operator<(const Query &r)const{
return x<r.x;
}
};
vector<Query> qvec[30002][2];
void addQuery1(int s, int e, int from, int q){
if(tribeGroupA[s][from].empty() || tribeGroupA[e][from].empty()) return;
for(int x: tribeGroupA[s][from]){
int aidx = upper_bound(all(tribeGroupA[e][from]), x, [&](int A, int B){return ccw(pointA[A],pointA[B])<0;}) - tribeGroupA[e][from].begin();
int bidx = upper_bound(all(tribeGroupB[e][from]), x, [&](int A, int B){return ccw(pointB[A],pointB[B])<0;}) - tribeGroupB[e][from].begin();
if(from == 0) qvec[e][0].push_back(Query(aidx-1, 0, bidx-1, -1, q));
else qvec[e][1].push_back(Query(aidx-1, bidx, (int)tribeGroupB[e][from].size()-1, 1, q));
}
}
void addQuery2(int s, int e, int from, int q){
if(tribeGroupA[s][from].empty() || tribeGroupA[e][from].empty()) return;
for(int x: tribeGroupA[e][from]){
int aidx = upper_bound(all(tribeGroupA[s][from]), x, [&](int A, int B){return ccw(pointA[A],pointA[B])<0;}) - tribeGroupA[s][from].begin();
int bidx = upper_bound(all(tribeGroupB[s][from]), x, [&](int A, int B){return ccw(pointB[A],pointB[B])<0;}) - tribeGroupB[s][from].begin();
if(from == 0) qvec[s][0].push_back(Query(aidx-1, bidx, (int)tribeGroupB[s][from].size()-1, 1, q));
else qvec[s][1].push_back(Query(aidx-1, 0, bidx-1, -1, q));
}
}
void solve(){
for(int i=1; i<=q; i++){
addAns(qx[i], qy[i], i);
addAns(qy[i], qx[i], i);
if(tribeCnt[qx[i]] < tribeCnt[qy[i]]) addQuery1(qx[i], qy[i], 0, i), addQuery1(qx[i], qy[i], 1, i);
else addQuery2(qx[i], qy[i], 0, i), addQuery2(qx[i], qy[i], 1, i);
}
for(int i=1; i<=m; i++){
for(int type=0; type<2; type++){
if(qvec[i][type].empty()) continue;
int pnt;
/// A
pnt = 0;
fenwick.init(tribeGroupB[i][type].size());
for(int j=-1; j<(int)tribeGroupA[i][type].size(); j++){
if(j>=0) fenwick.add(idxB[tribeGroupA[i][type][j]]+1, 1);
while(pnt < (int)qvec[i][type].size() && qvec[i][type][pnt].x == j){
Query p = qvec[i][type][pnt++];
ll val = fenwick.sum(p.yl+1, p.yr+1);
ans[p.q] += p.v==1 ? val : (p.yr - p.yl + 1) - val;
}
}
}
}
}
void output(){
for(int i=1; i<=q; i++){
printf("%d\n", ans[i]);
}
}
Compilation message
dragon2.cpp: In function 'void input()':
dragon2.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%lld %lld %d", &point[i].x, &point[i].y, &tribe[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%lld %lld %lld %lld", &la.x, &la.y, &lb.x, &lb.y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
dragon2.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d %d", &qx[i], &qy[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5460 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4034 ms |
5588 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5460 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
