| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27281 |
2017-07-12T07:02:29 Z |
김동현(#1138) |
Dragon 2 (JOI17_dragon2) |
C++14 |
|
133 ms |
31740 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Pos{ ll x, y; int c; };
int n, m, k, sz[30010], vs[2];
Pos a[30010], p[2];
vector<Pos> v[2], pv[2][2], cv[2][30010], cpv[2][2][30010], tcv[30010];
function<bool(Pos, Pos)> cmp[2];
struct Nod{
int v;
Nod *l, *r;
Nod() : v(0), l(nullptr), r(nullptr) {}
void ini(int ns, int ne){
if(ns == ne) return;
if(l == nullptr) l = new Nod();
if(r == nullptr) r = new Nod();
int m = (ns + ne) / 2;
l->ini(ns, m);
r->ini(m + 1, ne);
}
Nod *upd(int x, int ns, int ne){
if(x < ns || ne < x) return this;
Nod *ret = new Nod();
if(ns == ne){
ret->v++;
return ret;
}
int m = (ns + ne) / 2;
ret->l = l->upd(x, ns, m);
ret->r = r->upd(x, m + 1, ne);
ret->v = ret->l->v + ret->r->v;
return ret;
}
int get(int s, int e, int ns, int ne){
if(ne < s || e < ns) return 0;
if(s <= ns && ne <= e) return v;
int m = (ns + ne) / 2;
return l->get(s, e, ns, m) + r->get(s, e, m + 1, ne);
}
};
Nod *tr[2][30010];
vector<int> lst[2][30010];
int ccw(Pos a, Pos b, Pos c){
ll t = (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y);
return t < 0 ? -1 : t > 0 ? 1 : 0;
}
int ud(Pos x){ return ccw(p[0], p[1], x) > 0 ? 0 : 1; }
int wh(const vector<Pos> &v, Pos x, int i){
return int(lower_bound(v.begin(), v.end(), x, cmp[i]) - v.begin());
}
Pos trp(Pos p, Pos x){ return {2 * p.x - x.x, 2 * p.y - x.y}; }
int main(){
scanf("%d%d", &n, &m);
for(int i = 1, x, y, c; i <= n; i++){
scanf("%d%d%d", &x, &y, &c);
a[i] = {ll(x), ll(y), c};
sz[c]++;
}
scanf("%lld%lld%lld%lld%d", &p[0].x, &p[0].y, &p[1].x, &p[1].y, &k);
for(int i = 1; i <= n; i++){
v[ud(a[i])].push_back(a[i]);
cv[ud(a[i])][a[i].c].push_back(a[i]);
tcv[a[i].c].push_back(a[i]);
}
cmp[0] = [](Pos a, Pos b){ return ccw(p[0], a, b) > 0; };
cmp[1] = [](Pos a, Pos b){ return ccw(p[1], a, b) > 0; };
for(int i = 0; i < 2; i++){
vs[i] = v[i].size();
for(int j = 1; j <= m; j++) cpv[0][i][j] = cpv[1][i][j] = cv[i][j];
for(int j = 0; j < 2; j++){
pv[i][j] = v[j];
sort(pv[i][j].begin(), pv[i][j].end(), cmp[i]);
for(int t = 1; t <= m; t++)
sort(cpv[i][j][t].begin(), cpv[i][j][t].end(), cmp[i]);
}
}
for(int i = 0; i < 2; i++){
if(!vs[i]) continue;
tr[i][0] = new Nod();
tr[i][0]->ini(0, vs[i] - 1);
for(int j = 1; j <= m; j++) lst[i][j].push_back(0);
for(int j = 0; j < vs[i]; j++){
Pos cur = pv[!i][i][j];
tr[i][j + 1] = tr[i][lst[i][cur.c].back()]->upd(wh(pv[i][i], cur, i), 0, vs[i] - 1);
lst[i][cur.c].push_back(j + 1);
}
}
for(int x, y; k--; ){
scanf("%d%d", &x, &y);
int ans = 0;
int fl = 0; if(sz[x] > sz[y]){ swap(x, y); fl = 1; }
for(auto &i : tcv[x]){
int d = ud(i);
//int lans = ans;
ans += int(cv[!d][y].size());
auto t = lower_bound(cpv[d][!d][y].begin(), cpv[d][!d][y].end(), trp(p[d], i), cmp[d]);
ans -= int(t - cpv[d][!d][y].begin());
t = upper_bound(cpv[!d][!d][y].begin(), cpv[!d][!d][y].end(), trp(p[!d], i), cmp[!d]);
ans -= int(cpv[!d][!d][y].end() - t);
//printf("(%d, %d) : other side %d\n", i.x, i.y, ans - lans);
//lans = ans;
if(!vs[d]) break;
auto u = upper_bound(lst[d][y].begin(), lst[d][y].end(), wh(pv[!d][d], i, !d) + 1); u--;
ans += tr[d][*u]->get(wh(pv[d][d], i, d), vs[d] - 1, 0, vs[d] - 1);
if(!fl){
ans += int(cv[d][y].size());
t = lower_bound(cpv[!d][d][y].begin(), cpv[!d][d][y].end(), i, cmp[!d]);
ans -= int(t - cpv[!d][d][y].begin());
t = upper_bound(cpv[d][d][y].begin(), cpv[d][d][y].end(), i, cmp[d]);
ans -= int(cpv[d][d][y].end() - t);
}
//printf("(%d, %d) : same side %d\n", i.x, i.y, ans - lans);
}
//puts("----");
printf("%d\n", ans);
}
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:61:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
dragon2.cpp:63:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &c);
^
dragon2.cpp:67:69: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld%d", &p[0].x, &p[0].y, &p[1].x, &p[1].y, &k);
^
dragon2.cpp:97:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
31740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
