제출 #1323799

#제출 시각아이디문제언어결과실행 시간메모리
1323799Zbyszek99Dragon 2 (JOI17_dragon2)C++20
100 / 100
1589 ms93620 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int tree_siz = (1<<16)-1;
int sum[tree_siz+1];

int get_sum(int s1, int s2)
{
    int ans = 0;
    int l = tree_siz/2+s1+1;
    int r = tree_siz/2+s2+1;
    while(l < r)
    {
        if(l&1)
        {
            ans += sum[l];
            l++;
        }
        if((r&1)==0)
        {
            ans += sum[r];
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if(l == r) ans += sum[l];
    return ans;
}

void change(int ind, int x)
{
    int v = tree_siz/2+ind+1;
    while(v >= 1)
    {
        sum[v] += x;
        v /= 2;
    }
}

pll sort_mid;
bool is_right(pll a, pll b, pll c)
{
    return (a.ff-c.ff)*(b.ss-c.ss)-(a.ss-c.ss)*(b.ff-c.ff) >= 0;
}

struct point
{
    ll x,y;
    int ind;
    bool operator<(const point& other) const
    {
        return is_right({x,y},{other.x,other.y},sort_mid);
    }
};

vector<point> lp;
vector<point> rp;
int color[30001];
int ref_ind[30001];
vector<point> l_color[30001];
vector<point> r_color[30001];
ll color_ans[30001];
ll color_ans2[30001];
ll color_ans3[30001];
pll a,b;

ll calc_inter(vector<point>& l1, vector<point>& r1, vector<point>& l2, vector<point>& r2, bool ans_type = 0)
{
    ll ans = 0;
    // l1 - r2
    int cur2 = siz(r2)-1;
    for(int i = siz(l1)-1; i >= 0; i--)
    {
        while(cur2 >= 0 && is_right({r2[cur2].x,r2[cur2].y},{l1[i].x,l1[i].y},a)) change(ref_ind[r2[cur2--].ind],1);
        (!ans_type ? ans : color_ans[color[l1[i].ind]]) += get_sum(0,ref_ind[l1[i].ind]);
    }    
    for(int i = cur2+1; i < siz(r2); i++) change(ref_ind[r2[i].ind],-1);
    // l1 - l2
    cur2 = 0;
    for(int i = 0; i <= siz(l1)-1; i++)
    {
        while(cur2 < siz(l2) && is_right({l2[cur2].x,l2[cur2].y},{l1[i].x,l1[i].y},a)) change(ref_ind[l2[cur2++].ind],1);
        (!ans_type ? ans : color_ans2[color[l1[i].ind]]) += get_sum(ref_ind[l1[i].ind],tree_siz/2);
    }    
    rep(i,cur2) change(ref_ind[l2[i].ind],-1);
    // r1 - l2
    cur2 = 0;
    for(int i = 0; i <= siz(r1)-1; i++)
    {
        while(cur2 < siz(l2) && is_right({r1[i].x,r1[i].y},{l2[cur2].x,l2[cur2].y},a)) change(ref_ind[l2[cur2++].ind],1);
        (!ans_type ? ans : color_ans[color[r1[i].ind]]) += get_sum(ref_ind[r1[i].ind],tree_siz/2);
    }    
    rep(i,cur2) change(ref_ind[l2[i].ind],-1);
    // r1 - r2
    cur2 = siz(r2)-1;
    for(int i = siz(r1)-1; i >= 0; i--)
    {
        while(cur2 >= 0 && is_right({r1[i].x,r1[i].y},{r2[cur2].x,r2[cur2].y},a)) change(ref_ind[r2[cur2--].ind],1);
        (!ans_type ? ans : color_ans2[color[r1[i].ind]]) += get_sum(0,ref_ind[r1[i].ind]);
    }    
    for(int i = cur2+1; i < siz(r2); i++) change(ref_ind[r2[i].ind],-1);
    return ans;
}

void calc_inter2(vector<point>& l1, vector<point>& r1, vector<point>& l2, vector<point>& r2)
{
    // l1 - l2
    int cur2 = siz(l2)-1;
    for(int i = siz(l1)-1; i >= 0; i--)
    {
        while(cur2 >= 0 && is_right({l1[i].x,l1[i].y},{l2[cur2].x,l2[cur2].y},a)) change(ref_ind[l2[cur2--].ind],1);
        color_ans3[color[l1[i].ind]] += get_sum(0,ref_ind[l1[i].ind]);
    }
    for(int i = cur2+1; i <= siz(l2)-1; i++) change(ref_ind[l2[i].ind],-1);
    // r1 - r2
    cur2 = 0;
    for(int i = 0; i <= siz(r1)-1; i++)
    {
        while(cur2 < siz(r2) && is_right({r2[cur2].x,r2[cur2].y},{r1[i].x,r1[i].y},a)) change(ref_ind[r2[cur2++].ind],1);
        color_ans3[color[r1[i].ind]] += get_sum(ref_ind[r1[i].ind],tree_siz/2);
    }
    rep(i,cur2) change(ref_ind[r2[i].ind],-1);
}

ll prep_ans[30001][181];
ll prep_ans2[181][30001];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,m;
    cin >> n >> m;
    vector<point> points;
    rep(i,n)
    {
        ll x,y;
        int c;
        cin >> x >> y >> c;
        color[i] = c;
        points.pb({x,y,i});
    }
    map<int,int> cnt;
    forall(it,points) cnt[color[it.ind]]++;
    vector<pii> vs;
    rep2(i,1,m) vs.pb({cnt[i],i});
    sort(all(vs));
    reverse(all(vs));
    map<int,int> mp;
    int cur = 0;
    forall(it,vs) mp[it.ss] = cur++;
    rep(i,n) color[i] = mp[color[i]];
    cin >> a.ff >> a.ss >> b.ff >> b.ss;
    forall(it,points)
    {
        if(is_right(b,{it.x,it.y},a)) lp.pb(it);
        else rp.pb(it);
    }
    sort_mid = a;
    sort(all(lp));
    sort(all(rp));
    vector<point> ref_points;
    forall(it,lp) ref_points.pb(it);
    forall(it,rp) ref_points.pb({2*b.ff-it.x,2*b.ss-it.y,it.ind});
    sort_mid = b;
    sort(all(ref_points));
    cur = 1;
    forall(it,ref_points) ref_ind[it.ind] = cur++;
    forall(it,lp) l_color[color[it.ind]].pb(it);
    forall(it,rp) r_color[color[it.ind]].pb(it);
    rep(i,min(m,180))
    {
        calc_inter(lp,rp,l_color[i],r_color[i],1);
        calc_inter2(lp,rp,l_color[i],r_color[i]);
        rep(j,m)
        {
            prep_ans[j][i] = color_ans[j]+color_ans2[j];
            prep_ans2[i][j] = color_ans[j]+color_ans3[j];
            color_ans[j] = 0;
            color_ans2[j] = 0;
            color_ans3[j] = 0;
        }
    }
    int q;
    cin >> q;
    rep(qq,q)
    {
        int a2,b2;
        cin >> a2 >> b2;
        a2 = mp[a2];
        b2 = mp[b2];
        if(a2 < 180) cout << prep_ans2[a2][b2] << "\n";
        else if(b2 < 180) cout << prep_ans[a2][b2] << "\n";
        else cout << calc_inter(l_color[a2],r_color[a2],l_color[b2],r_color[b2]) << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...