답안 #69438 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69438	2018-08-20T20:55:00 Z	Benq	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	2161 ms	12580 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; co.fill(0);
    for (int a: member[x]) {
        z.toUpd.pb({BOUND[a].f.f,BOUND[a].s.f,1});
        z.toUpd.pb({BOUND[a].f.s,BOUND[a].s.s,1});
        z.toUpd.pb({BOUND[a].f.f,BOUND[a].s.s,-1});
        z.toUpd.pb({BOUND[a].f.s,BOUND[a].s.f,-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 ((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;
    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;
    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]) {
            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	10 ms	3000 KB	Output is correct
2	Correct	21 ms	3300 KB	Output is correct
3	Correct	136 ms	3576 KB	Output is correct
4	Correct	185 ms	6732 KB	Output is correct
5	Correct	82 ms	7128 KB	Output is correct
6	Correct	8 ms	7128 KB	Output is correct
7	Correct	7 ms	7128 KB	Output is correct
8	Correct	9 ms	7128 KB	Output is correct
9	Correct	8 ms	7128 KB	Output is correct
10	Correct	8 ms	7128 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	7868 KB	Output is correct
2	Correct	202 ms	8456 KB	Output is correct
3	Correct	87 ms	8456 KB	Output is correct
4	Correct	42 ms	8456 KB	Output is correct
5	Correct	38 ms	8456 KB	Output is correct
6	Correct	72 ms	8456 KB	Output is correct
7	Correct	70 ms	8456 KB	Output is correct
8	Correct	73 ms	8456 KB	Output is correct
9	Correct	52 ms	8456 KB	Output is correct
10	Correct	62 ms	8456 KB	Output is correct

Subtask #3
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	3000 KB	Output is correct
2	Correct	21 ms	3300 KB	Output is correct
3	Correct	136 ms	3576 KB	Output is correct
4	Correct	185 ms	6732 KB	Output is correct
5	Correct	82 ms	7128 KB	Output is correct
6	Correct	8 ms	7128 KB	Output is correct
7	Correct	7 ms	7128 KB	Output is correct
8	Correct	9 ms	7128 KB	Output is correct
9	Correct	8 ms	7128 KB	Output is correct
10	Correct	8 ms	7128 KB	Output is correct
11	Correct	73 ms	7868 KB	Output is correct
12	Correct	202 ms	8456 KB	Output is correct
13	Correct	87 ms	8456 KB	Output is correct
14	Correct	42 ms	8456 KB	Output is correct
15	Correct	38 ms	8456 KB	Output is correct
16	Correct	72 ms	8456 KB	Output is correct
17	Correct	70 ms	8456 KB	Output is correct
18	Correct	73 ms	8456 KB	Output is correct
19	Correct	52 ms	8456 KB	Output is correct
20	Correct	62 ms	8456 KB	Output is correct
21	Correct	74 ms	8456 KB	Output is correct
22	Correct	206 ms	8456 KB	Output is correct
23	Correct	1423 ms	8456 KB	Output is correct
24	Correct	2161 ms	8876 KB	Output is correct
25	Correct	234 ms	8876 KB	Output is correct
26	Correct	134 ms	9172 KB	Output is correct
27	Correct	57 ms	9172 KB	Output is correct
28	Correct	71 ms	9172 KB	Output is correct
29	Incorrect	252 ms	12580 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #69438

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
0 / 40.0