답안 #69443 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69443	2018-08-20T21:09:40 Z	Benq	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	3317 ms	23108 KB

dragon2

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 30001;
 
const ld PI = 4*atan((ld)1);
 
namespace geo {
    istream& operator>> (istream& is, pi& p) {
        is >> p.f >> p.s;
        return is;
    }
    void nor(pd& x) { if (x.f < -PI) x.f += 2*PI, x.s += 2*PI; }
    ld area(cd a, cd b, cd c) { return (conj(b-a)*(c-a)).imag(); }
    pi operator-(const pi& l, const pi& r) { return {l.f-r.f,l.s-r.s}; }
}

using namespace geo;

struct BIT {
    vector<array<int,3>> toUpd;
    vector<pair<array<int,3>,int*>> toQuery;
    vi m, bit;
    
    void clr() {
        toUpd.clear(), toQuery.clear(), m.clear(), bit.clear();
    }
    
    void upd(int x, int y) {
        for (int X = ub(all(m),x)-m.begin()-1; X < sz(bit); X += (X&-X))
            bit[X] += y;
    }
    
    void query(int x, int y, int* z) {
        for (int X = ub(all(m),x)-m.begin()-1; X; X -= (X&-X)) 
            (*z) += y*bit[X];
    }
    
    void prop() {
        for (auto x: toUpd) m.pb(x[1]);
        m.pb(-MOD); sort(all(m)); m.erase(unique(all(m)),m.end());
        bit.resize(sz(m));
        sort(all(toUpd)), sort(all(toQuery));
        
        int ind = 0;
        for (auto x: toQuery) {
            while (ind < sz(toUpd) && toUpd[ind][0] <= x.f[0]) {
                upd(toUpd[ind][1],toUpd[ind][2]);
                ind ++;
            } 
            query(x.f[1],x.f[2],x.s);
        }
    }
};

int N,M,group[MX],ans[100001];
vi member[MX];
pi pos[MX], h[2];
pi POS[MX];
pair<pi,pi> BOUND[MX];
vpi query[MX], query2[MX];
BIT z;

void process1(int x) {
    z.clr();
    array<int,MX> co = array<int,MX>(); 
    for (int a: member[x]) {
        z.toUpd.pb({BOUND[a].f.f+1,BOUND[a].s.f+1,1});
        z.toUpd.pb({BOUND[a].f.s+1,BOUND[a].s.s+1,1});
        z.toUpd.pb({BOUND[a].f.f+1,BOUND[a].s.s+1,-1});
        z.toUpd.pb({BOUND[a].f.s+1,BOUND[a].s.f+1,-1});
    }
    FOR(a,1,N+1) {
        z.toQuery.pb({{POS[a].f,POS[a].s,1},&co[group[a]]});
        z.toQuery.pb({{POS[a].f+N,POS[a].s,1},&co[group[a]]});
        z.toQuery.pb({{POS[a].f,POS[a].s+N,1},&co[group[a]]});
        z.toQuery.pb({{POS[a].f+N,POS[a].s+N,1},&co[group[a]]});
    }
    z.prop(); 
    for (auto a: query[x]) ans[a.s] = co[a.f]; 
}

void process2(int x) {
    for (auto a: query[x]) query2[a.f].pb({x,a.s}); 
}

void process(int x) {
    //if (sz(query[x])) process1(x);
    if ((ll)sz(member[x])*sz(query[x]) >= N) process1(x);
    else process2(x);
}

int half(pi x) {
    if (x.s != 0) return x.s > 0;
    return x.f > 0;
}

ll area(pi a, pi b) {
    return (ll)a.f*b.s-(ll)a.s*b.f;
}

ll area(pi a, pi b, pi c) {
    b.f -= a.f, b.s -= a.s;
    c.f -= a.f, c.s -= a.s;
    return area(b,c);
}

bool cmp(pi a, pi b) {
    if (half(a) != half(b)) return half(a) < half(b);
    return area(a,b) > 0;
}

pi nor(pi x) {
    while (x.f < 0) x.f += N, x.s += N;
    while (x.f >= N) x.f -= N, x.s -= N;
    /*if (x.s < 0 || x.s > 2*N-1 || x.s <= x.f || x.s > x.f+N) {
        cerr << " " << x.f << " " << x.s << "\n";
        exit(0);
    }*/
    return x;
}

void genCoordinate(int ind) {
    vector<pair<pi,int>> v;
    FOR(i,1,N+1) v.pb({pos[i]-h[ind],i});
    sort(all(v),[](auto a, auto b) { return cmp(a.f,b.f); });
    int cur = 0;
    F0R(i,N) {
        while (cur < i+N && area(v[i].f,v[cur%N].f) >= 0) cur ++;
        if (ind == 0) POS[v[i].s].f = i;
        else POS[v[i].s].s = i;
        
        if (area(h[0],h[1],pos[v[i].s]) > 0) {
            if (ind == 0) BOUND[v[i].s].f = nor({cur-1,i+N-1});
            else BOUND[v[i].s].s = nor({i,cur-1});
        } else {
            if (ind == 0) BOUND[v[i].s].f = nor({i,cur-1});
            else BOUND[v[i].s].s = nor({cur-1,i+N-1});
        }
    }
}

void input() {
    //freopen("Input.txt","r",stdin);
    //freopen("Output.txt","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    FOR(i,1,N+1) {
        cin >> pos[i] >> group[i];
        member[group[i]].pb(i);
    }
    cin >> h[0] >> h[1];
    genCoordinate(0);
    genCoordinate(1);
}
 
int main() {
    input();
    int Q; cin >> Q; // Q = 50;
    F0R(i,Q) {
        int f,g; cin >> f >> g;
        query[f].pb({g,i});
    }
    FOR(i,1,M+1) process(i);
    FOR(i,1,M+1) {
        z.clr();
        for (auto a: query2[i]) for (int b: member[a.f]) {
            assert(group[b] != i);
            z.toQuery.pb({{BOUND[b].f.s,BOUND[b].s.s,1},&ans[a.s]});
            z.toQuery.pb({{BOUND[b].f.f,BOUND[b].s.s,-1},&ans[a.s]});
            z.toQuery.pb({{BOUND[b].f.s,BOUND[b].s.f,-1},&ans[a.s]});
            z.toQuery.pb({{BOUND[b].f.f,BOUND[b].s.f,1},&ans[a.s]});
        }
        for (int a: member[i]) {
            z.toUpd.pb({POS[a].f,POS[a].s,1});
            z.toUpd.pb({POS[a].f+N,POS[a].s,1});
            z.toUpd.pb({POS[a].f,POS[a].s+N,1});
            z.toUpd.pb({POS[a].f+N,POS[a].s+N,1});
        }
        z.prop();
    }
    F0R(i,Q) cout << ans[i] << "\n";
}
 
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	3000 KB	Output is correct
2	Correct	25 ms	3292 KB	Output is correct
3	Correct	120 ms	3420 KB	Output is correct
4	Correct	252 ms	6708 KB	Output is correct
5	Correct	105 ms	8148 KB	Output is correct
6	Correct	12 ms	8148 KB	Output is correct
7	Correct	11 ms	8148 KB	Output is correct
8	Correct	14 ms	8148 KB	Output is correct
9	Correct	11 ms	8148 KB	Output is correct
10	Correct	12 ms	8148 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	89 ms	9076 KB	Output is correct
2	Correct	234 ms	10300 KB	Output is correct
3	Correct	83 ms	10300 KB	Output is correct
4	Correct	48 ms	10300 KB	Output is correct
5	Correct	52 ms	10300 KB	Output is correct
6	Correct	82 ms	10332 KB	Output is correct
7	Correct	80 ms	10412 KB	Output is correct
8	Correct	88 ms	10412 KB	Output is correct
9	Correct	75 ms	10412 KB	Output is correct
10	Correct	60 ms	10412 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	3000 KB	Output is correct
2	Correct	25 ms	3292 KB	Output is correct
3	Correct	120 ms	3420 KB	Output is correct
4	Correct	252 ms	6708 KB	Output is correct
5	Correct	105 ms	8148 KB	Output is correct
6	Correct	12 ms	8148 KB	Output is correct
7	Correct	11 ms	8148 KB	Output is correct
8	Correct	14 ms	8148 KB	Output is correct
9	Correct	11 ms	8148 KB	Output is correct
10	Correct	12 ms	8148 KB	Output is correct
11	Correct	89 ms	9076 KB	Output is correct
12	Correct	234 ms	10300 KB	Output is correct
13	Correct	83 ms	10300 KB	Output is correct
14	Correct	48 ms	10300 KB	Output is correct
15	Correct	52 ms	10300 KB	Output is correct
16	Correct	82 ms	10332 KB	Output is correct
17	Correct	80 ms	10412 KB	Output is correct
18	Correct	88 ms	10412 KB	Output is correct
19	Correct	75 ms	10412 KB	Output is correct
20	Correct	60 ms	10412 KB	Output is correct
21	Correct	84 ms	10468 KB	Output is correct
22	Correct	217 ms	10680 KB	Output is correct
23	Correct	1480 ms	11032 KB	Output is correct
24	Correct	2360 ms	11464 KB	Output is correct
25	Correct	273 ms	11464 KB	Output is correct
26	Correct	171 ms	11804 KB	Output is correct
27	Correct	48 ms	11804 KB	Output is correct
28	Correct	50 ms	11804 KB	Output is correct
29	Correct	220 ms	15088 KB	Output is correct
30	Correct	208 ms	15276 KB	Output is correct
31	Correct	220 ms	15540 KB	Output is correct
32	Correct	218 ms	15540 KB	Output is correct
33	Correct	2498 ms	15540 KB	Output is correct
34	Correct	196 ms	15540 KB	Output is correct
35	Correct	169 ms	15540 KB	Output is correct
36	Correct	161 ms	15540 KB	Output is correct
37	Correct	163 ms	15540 KB	Output is correct
38	Correct	2683 ms	15540 KB	Output is correct
39	Correct	3317 ms	16068 KB	Output is correct
40	Correct	2348 ms	16068 KB	Output is correct
41	Correct	225 ms	19412 KB	Output is correct
42	Correct	327 ms	20772 KB	Output is correct
43	Correct	439 ms	22116 KB	Output is correct
44	Correct	119 ms	22116 KB	Output is correct
45	Correct	152 ms	22116 KB	Output is correct
46	Correct	165 ms	23108 KB	Output is correct
47	Correct	90 ms	23108 KB	Output is correct
48	Correct	83 ms	23108 KB	Output is correct
49	Correct	93 ms	23108 KB	Output is correct

답안 #69443

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 40.0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
40.0 / 40.0