| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27290 |
2017-07-12T07:11:18 Z |
구사과(#1145) |
Dragon 2 (JOI17_dragon2) |
C++14 |
|
1839 ms |
13836 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
struct pnt{
int x, y, c;
int r1, r2;
}a[30005], s, e;
lint ccw(pnt a, pnt b, pnt c){
return 1ll * (b.x - a.x) * (c.y - a.y) - 1ll * (c.x - a.x) * (b.y - a.y);
}
int n, m;
int stx[30005], sty[30005], edx[30005], edy[30005];
void label1(){
sort(a, a+n, [&](const pnt &p, const pnt &q){
bool bh1 = ccw(s, e, p) > 0;
bool bh2 = ccw(s, e, q) > 0;
if(bh1 != bh2) return bh1 > bh2;
return ccw(s, p, q) > 0;
});
int dv = 0;
for(int i=0; i<n; i++){
a[i].r1 = i;
if(ccw(s, e, a[i]) > 0) dv = i+1;
}
int p = 0;
for(int i=dv; i<n; i++){
while(p < dv && ccw(s, a[i], a[p]) > 0) p++;
stx[i] = i;
edx[i] = p;
}
p = dv;
for(int i=0; i<dv; i++){
while(p < n && ccw(s, a[i], a[p]) > 0) p++;
stx[i] = p;
edx[i] = i;
}
}
void label2(){
sort(a, a+n, [&](const pnt &p, const pnt &q){
bool bh1 = ccw(s, e, p) > 0;
bool bh2 = ccw(s, e, q) > 0;
if(bh1 != bh2) return bh1 > bh2;
return ccw(e, p, q) > 0;
});
int dv = 0;
for(int i=0; i<n; i++){
a[i].r2 = i;
if(ccw(s, e, a[i]) > 0) dv = i+1;
}
int p = 0;
for(int i=dv; i<n; i++){
while(p < dv && ccw(e, a[i], a[p]) > 0) p++;
sty[i] = p;
edy[i] = i;
}
p = dv;
for(int i=0; i<dv; i++){
while(p < n && ccw(e, a[i], a[p]) > 0) p++;
sty[i] = i;
edy[i] = p;
}
}
vector<pi> grp[30005];
map<pi, int> mp;
int refer[100005], ans[100005];
struct sweep1{
int pos, s, e, dx, idx;
bool operator<(const sweep1 &c)const{
return pos < c.pos;
}
};
vector<sweep1> s1[30005];
void add_sweep(int sx, int ex, int sy, int ey, int gnum, int idx){
if(sx > ex || sy > ey) return;
s1[gnum].push_back({sx - 1, sy, ey, -1, idx});
s1[gnum].push_back({ex, sy, ey, 1, idx});
}
void add_sweep2(int y, int gnum, int idx){
for(auto &i : grp[gnum]){
if(sty[i.second] <= y && y < edy[i.second]) ans[idx]++;
}
}
void add_sweep3(int x, int y, int gnum, int idx){
for(auto &i : grp[gnum]){
if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
}
}
struct bit{
int tree[30005];
void add(int x, int v){
x += 2;
while(x <= n+2){
tree[x] += v;
x += x & -x;
}
}
int query(int x){
int ret = 0;
while(x){
ret += tree[x];
x -= x & -x;
}
return ret;
}
}bit;
void proc_sweep(int gnum){
sort(s1[gnum].begin(), s1[gnum].end());
sort(grp[gnum].begin(), grp[gnum].end());
int p = 0;
for(auto &i : s1[gnum]){
while(p < grp[gnum].size() && grp[gnum][p].first <= i.pos){
bit.add(grp[gnum][p++].second, 1);
}
ans[i.idx] += i.dx * (bit.query(i.e) - bit.query(i.s - 1));
}
while(p > 0){
bit.add(grp[gnum][--p].second, -1);
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=0; i<n; i++){
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
}
scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
label1();
label2();
for(int i=0; i<n; i++){
grp[a[i].c].push_back(pi(a[i].r1, a[i].r2));
}
int q;
scanf("%d",&q);
for(int i=1; i<=q; i++){
int x, y;
scanf("%d %d",&x,&y);
if(mp.find(pi(x, y)) != mp.end()){
refer[i] = mp[pi(x, y)];
continue;
}
if(grp[x].size() < grp[y].size()){
for(auto &j : grp[x]){
add_sweep(0, edx[j.first] - 1, sty[j.second], edy[j.second] - 1, y, i);
add_sweep(stx[j.first], n-1, sty[j.second], edy[j.second] - 1, y, i);
}
}
else{
for(auto &j : grp[y]){
add_sweep2(j.second, x, i);
add_sweep3(j.first, j.second, x, i);
}
}
mp[pi(x, y)] = i;
}
for(int i=1; i<=m; i++) proc_sweep(i);
for(int i=1; i<=q; i++){
if(refer[i]) printf("%d\n", ans[refer[i]]);
else printf("%d\n", ans[i]);
}
}
Compilation message
dragon2.cpp: In function 'void proc_sweep(int)':
dragon2.cpp:126:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p < grp[gnum].size() && grp[gnum][p].first <= i.pos){
^
dragon2.cpp: In function 'int main()':
dragon2.cpp:137:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
^
dragon2.cpp:139:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
^
dragon2.cpp:141:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
^
dragon2.cpp:148:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
dragon2.cpp:151:23: 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 |
Correct |
13 ms |
5400 KB |
Output is correct |
| 2 |
Runtime error |
13 ms |
6448 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1329 ms |
5800 KB |
Output is correct |
| 2 |
Runtime error |
1839 ms |
13836 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
5400 KB |
Output is correct |
| 2 |
Runtime error |
13 ms |
6448 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
