| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27276 |
2017-07-12T06:54:30 Z |
김현수(#1143) |
Dragon 2 (JOI17_dragon2) |
C++14 |
|
409 ms |
44148 KB |
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 30005;
ll n, m, q, s1, s2, ans[N];
pll p1, p2, qry[N], piv;
map<pll, ll> mem;
vector<ll> z1, z2;
vector<pll> drg[N], cp, pt;
struct data {pll s[2], e[2]; ll i;};
vector<data> rd[N];
struct sweep {ll s, e, x, i;};
vector<sweep> swp[N];
struct segtree {
ll v[555555], lim;
void init () {
for(lim=1;lim<=s2;lim<<=1);
for(ll i=2*lim;--i;) v[i] = 0;
}
void upd (ll P, ll V) {
P += lim;
while(P) {v[P] += V; P >>= 1;}
}
ll get (ll S, ll E) {
S += lim; E += lim;
ll ret = 0;
while(S <= E) {
if(S%2==1) ret += v[S++];
if(E%2==0) ret += v[E--];
S >>= 1; E >>= 1;
}
return ret;
}
} seg;
ll ccw (const pll &A, const pll &B, const pll &C) {
return (A.X*B.Y+B.X*C.Y+C.X*A.Y) - (A.Y*B.X+B.Y*C.X+C.Y*A.X);
}
bool isup (const pll &A, const pll &B) {
return (A.Y < B.Y || (A.Y == B.Y && A.X < B.X));
}
bool cmp (const pll &A, const pll &B) {
bool F1 = isup(piv, A), F2 = isup(piv, B);
if(F1 != F2) return F1;
return ccw(piv, A, B) > 0;
}
void cpr (pll &P, vector<pll> &D, vector<data> &R, int O, vector<ll> &V, ll &S) {
cp.clear(); V.clear(); piv = P;
for(auto &T : D) cp.push_back(T);
for(auto &T : R) {
cp.push_back(T.s[O]);
cp.push_back(T.e[O]);
}
sort(cp.begin(), cp.end(), cmp);
cp.erase(unique(cp.begin(), cp.end()), cp.end());
S = cp.size();
for(auto &T : D) {
V.push_back(lower_bound(cp.begin(), cp.end(), T, cmp) - cp.begin() + 1);
}
for(auto &T : R) {
T.s[O].X = lower_bound(cp.begin(), cp.end(), T.s[O], cmp) - cp.begin() + 1;
T.e[O].X = lower_bound(cp.begin(), cp.end(), T.e[O], cmp) - cp.begin() + 1;
}
}
void add (ll XS, ll XE, ll YS, ll YE, ll I) {
if(XS > XE) {
add(XS, s1, YS, YE, I);
add(1, XE, YS, YE, I);
}
else if(YS > YE) {
add(XS, XE, YS, s2, I);
add(XS, XE, 1, YE, I);
}
else {
swp[XE].push_back({YS, YE, 1, I});
swp[XS-1].push_back({YS, YE, -1, I});
}
}
pll Flip (const pll &A, const pll &B) {
return pll(2*A.X - B.X, 2*A.Y - B.Y);
}
void sadi (ll S, ll M, ll I) {
for(auto &T : drg[S]) {
data C; C.i = I;
C.s[0] = T; C.e[0] = Flip(p1, T);
if(ccw(p1, C.s[0], p2) < 0) swap(C.s[0], C.e[0]);
C.s[1] = T; C.e[1] = Flip(p2, T);
if(ccw(p2, C.s[1], p1) < 0) swap(C.s[1], C.e[1]);
rd[M].push_back(C);
}
}
void majo (ll S, ll M, ll I) {
for(auto &T : drg[M]) {
data C; C.i = I;
C.s[0] = p2; C.e[0] = Flip(p1, T);
if(ccw(p1, C.s[0], C.e[0]) < 0) swap(C.s[0], C.e[0]);
C.s[1] = p1; C.e[1] = Flip(p2, T);
if(ccw(p2, C.s[1], C.e[1]) < 0) swap(C.s[1], C.e[1]);
rd[S].push_back(C);
}
for(auto &T : drg[M]) {
data C; C.i = I;
C.s[0] = T; C.e[0] = Flip(p1, T);
if(ccw(p1, C.s[0], p2) > 0) swap(C.s[0], C.e[0]);
C.s[1] = T; C.e[1] = Flip(p2, T);
if(ccw(p2, C.s[1], p1) > 0) swap(C.s[1], C.e[1]);
rd[S].push_back(C);
}
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) {
ll A, B, C;
scanf("%lld%lld%lld",&A,&B,&C);
drg[C].push_back(pll(A, B));
}
scanf("%lld%lld%lld%lld%lld",&p1.X,&p1.Y,&p2.X,&p2.Y,&q);
for(ll i=1;i<=q;i++) {
ll A, B;
scanf("%lld%lld",&A, &B);
qry[i] = pll(A, B);
if(!mem[qry[i]]) {
mem[qry[i]] = 1;
if(drg[A].size() < drg[B].size()) sadi(A, B, i);
else majo(A, B, i);
}
}
for(ll i=1;i<=m;i++) {
cpr(p1, drg[i], rd[i], 0, z1, s1);
cpr(p2, drg[i], rd[i], 1, z2, s2);
for(ll j=0;j<=s1;j++) swp[j].clear();
for(auto &T : rd[i]) {
add(T.s[0].X, T.e[0].X, T.s[1].X, T.e[1].X, T.i);
}
seg.init(); pt.clear();
for(ll j=0;j<drg[i].size();j++) {
pt.push_back(pll(z1[j], z2[j]));
}
sort(pt.begin(), pt.end());
for(ll j=1,k=0;j<=s1;j++) {
while(k < pt.size() && pt[k].X <= j) {
seg.upd(pt[k].Y, 1); k++;
}
for(auto &T : swp[j]) {
ans[T.i] += seg.get(T.s, T.e) * T.x;
}
}
}
for(ll i=1;i<=q;i++) {
mem[qry[i]] += ans[i];
printf("%lld\n", mem[qry[i]]-1);
}
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:153:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<drg[i].size();j++) {
^
dragon2.cpp:158:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(k < pt.size() && pt[k].X <= j) {
^
dragon2.cpp:128:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&n,&m);
^
dragon2.cpp:131:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&A,&B,&C);
^
dragon2.cpp:134:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld%lld",&p1.X,&p1.Y,&p2.X,&p2.Y,&q);
^
dragon2.cpp:137:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&A, &B);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
10412 KB |
Output is correct |
| 2 |
Correct |
43 ms |
13476 KB |
Output is correct |
| 3 |
Correct |
409 ms |
44148 KB |
Output is correct |
| 4 |
Runtime error |
76 ms |
27568 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
16704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
10412 KB |
Output is correct |
| 2 |
Correct |
43 ms |
13476 KB |
Output is correct |
| 3 |
Correct |
409 ms |
44148 KB |
Output is correct |
| 4 |
Runtime error |
76 ms |
27568 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
