| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27305 |
2017-07-12T07:35:04 Z |
khsoo01 |
Dragon 2 (JOI17_dragon2) |
C++11 |
|
3766 ms |
262144 KB |
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n, m, q, s1, s2, ans[100005];
pll p1, p2, qry[100005], piv;
map<pll, ll> mem;
vector<ll> z1, z2;
vector<pll> drg[30005], cp, pt;
struct data {pll s[2], e[2]; int i;};
vector<data> rd[30005];
struct sweep {int s, e, x, i;};
vector<sweep> swp[1111111];
struct segtree {
int v[2222222], lim;
void init () {
for(lim=1;lim<=2*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) {
swp[XE].push_back({YS, YE+(YS>YE)*s2, 1, I});
swp[XS-1].push_back({YS, YE+(YS>YE)*s2, -1, I});
if(XS > XE) swp[s1].push_back({YS, YE+(YS>YE)*s2, 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() > 2*drg[B].size()) majo(A, B, i);
else sadi(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(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);
seg.upd(pt[k].Y+s2, 1);
k++;
}
for(auto &T : swp[j]) {
ans[T.i] += seg.get(T.s, T.e) * T.x;
}
swp[j].clear();
}
}
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 'void add(ll, ll, ll, ll, ll)':
dragon2.cpp:77:45: warning: narrowing conversion of 'YS' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
swp[XE].push_back({YS, YE+(YS>YE)*s2, 1, I});
^
dragon2.cpp:77:27: warning: narrowing conversion of '(((YS > YE) * s2) + YE)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
swp[XE].push_back({YS, YE+(YS>YE)*s2, 1, I});
^
dragon2.cpp:77:45: warning: narrowing conversion of 'I' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
swp[XE].push_back({YS, YE+(YS>YE)*s2, 1, I});
^
dragon2.cpp:78:48: warning: narrowing conversion of 'YS' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
swp[XS-1].push_back({YS, YE+(YS>YE)*s2, -1, I});
^
dragon2.cpp:78:29: warning: narrowing conversion of '(((YS > YE) * s2) + YE)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
swp[XS-1].push_back({YS, YE+(YS>YE)*s2, -1, I});
^
dragon2.cpp:78:48: warning: narrowing conversion of 'I' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
swp[XS-1].push_back({YS, YE+(YS>YE)*s2, -1, I});
^
dragon2.cpp:79:57: warning: narrowing conversion of 'YS' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
if(XS > XE) swp[s1].push_back({YS, YE+(YS>YE)*s2, 1, I});
^
dragon2.cpp:79:39: warning: narrowing conversion of '(((YS > YE) * s2) + YE)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
if(XS > XE) swp[s1].push_back({YS, YE+(YS>YE)*s2, 1, I});
^
dragon2.cpp:79:57: warning: narrowing conversion of 'I' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
if(XS > XE) swp[s1].push_back({YS, YE+(YS>YE)*s2, 1, I});
^
dragon2.cpp: In function 'int main()':
dragon2.cpp:142:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j<drg[i].size();j++) {
^
dragon2.cpp:147:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(k < pt.size() && pt[k].X <= j) {
^
dragon2.cpp:118: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:121: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:124: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:127:26: 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 |
41088 KB |
Output is correct |
| 2 |
Correct |
29 ms |
42532 KB |
Output is correct |
| 3 |
Correct |
263 ms |
57436 KB |
Output is correct |
| 4 |
Correct |
613 ms |
75924 KB |
Output is correct |
| 5 |
Correct |
296 ms |
53060 KB |
Output is correct |
| 6 |
Correct |
9 ms |
40904 KB |
Output is correct |
| 7 |
Correct |
16 ms |
40772 KB |
Output is correct |
| 8 |
Correct |
9 ms |
41000 KB |
Output is correct |
| 9 |
Correct |
16 ms |
41120 KB |
Output is correct |
| 10 |
Correct |
13 ms |
41004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
45124 KB |
Output is correct |
| 2 |
Correct |
436 ms |
60576 KB |
Output is correct |
| 3 |
Correct |
79 ms |
45200 KB |
Output is correct |
| 4 |
Correct |
33 ms |
41564 KB |
Output is correct |
| 5 |
Correct |
29 ms |
41300 KB |
Output is correct |
| 6 |
Correct |
86 ms |
44956 KB |
Output is correct |
| 7 |
Correct |
86 ms |
44824 KB |
Output is correct |
| 8 |
Correct |
79 ms |
44824 KB |
Output is correct |
| 9 |
Correct |
56 ms |
44956 KB |
Output is correct |
| 10 |
Correct |
63 ms |
44956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
41088 KB |
Output is correct |
| 2 |
Correct |
29 ms |
42532 KB |
Output is correct |
| 3 |
Correct |
263 ms |
57436 KB |
Output is correct |
| 4 |
Correct |
613 ms |
75924 KB |
Output is correct |
| 5 |
Correct |
296 ms |
53060 KB |
Output is correct |
| 6 |
Correct |
9 ms |
40904 KB |
Output is correct |
| 7 |
Correct |
16 ms |
40772 KB |
Output is correct |
| 8 |
Correct |
9 ms |
41000 KB |
Output is correct |
| 9 |
Correct |
16 ms |
41120 KB |
Output is correct |
| 10 |
Correct |
13 ms |
41004 KB |
Output is correct |
| 11 |
Correct |
99 ms |
45124 KB |
Output is correct |
| 12 |
Correct |
436 ms |
60576 KB |
Output is correct |
| 13 |
Correct |
79 ms |
45200 KB |
Output is correct |
| 14 |
Correct |
33 ms |
41564 KB |
Output is correct |
| 15 |
Correct |
29 ms |
41300 KB |
Output is correct |
| 16 |
Correct |
86 ms |
44956 KB |
Output is correct |
| 17 |
Correct |
86 ms |
44824 KB |
Output is correct |
| 18 |
Correct |
79 ms |
44824 KB |
Output is correct |
| 19 |
Correct |
56 ms |
44956 KB |
Output is correct |
| 20 |
Correct |
63 ms |
44956 KB |
Output is correct |
| 21 |
Correct |
83 ms |
45132 KB |
Output is correct |
| 22 |
Correct |
433 ms |
60380 KB |
Output is correct |
| 23 |
Correct |
3766 ms |
195956 KB |
Output is correct |
| 24 |
Memory limit exceeded |
396 ms |
262144 KB |
Memory limit exceeded |
| 25 |
Halted |
0 ms |
0 KB |
- |
