oj.uz

Submission #595029

# Submission time Handle Problem Language Result Execution time Memory
595029 2022-07-13T09:14:55 Z 반딧불(#8437) Dragon 2 (JOI17_dragon2) C++17
60 / 100
 4000 ms 12240 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Frac{
    ll a, b;
    Frac(){}
    Frac(ll a, ll b): a(a), b(b){
        ll g = __gcd(a, b);
        a/=g, b/=g;
        if(b<0) a=-a, b=-b;
    }

    bool operator<(const Frac &r)const{
        return a*r.b < b*r.a;
    }
};

struct vector2{
    ll x, y;
    vector2(){}
    vector2(ll x, ll y): x(x), y(y){}

    vector2 operator+(const vector2 &r)const{
        return vector2(x+r.x, y+r.y);
    }

    vector2 operator-(const vector2 &r)const{
        return vector2(x-r.x, y-r.y);
    }

    ll cross(vector2 r)const{
        return x*r.y - y*r.x;
    }

    bool operator<(const vector2 &r)const{
        return cross(r) > 0;
    }
};

struct Query{
    int x, y, idx;
    Query(){}
    Query(int x, int y, int idx): x(x), y(y), idx(idx){}
    bool operator<(const Query &r)const{
        return x==r.x ? y<r.y : x<r.x;
    }
};

ll ccw(vector2 a, vector2 b){
    return a.cross(b);
}

ll ccw(vector2 a, vector2 b, vector2 c){
    return (b-a).cross(c-a);
}

inline ll sign(ll x){
    return x>0?1:-1;
}

int n, k, q;
vector2 arr[30002];
int group[30002];
ll calc[30002];
vector<int> groupList[30002][2];
vector2 ps, pe;

int ans[100002];
Query query[100002];

void input();
void operate();

int main(){
    input();
    operate();
}

void input(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %d", &arr[i].x, &arr[i].y, &group[i]);
    }
    scanf("%lld %lld %lld %lld %d", &ps.x, &ps.y, &pe.x, &pe.y, &q);
    for(int i=1; i<=q; i++){
        scanf("%d %d", &query[i].x, &query[i].y);
        query[i].idx = i;
    }
}

void makePositive(){ /// ps�� 0����, pe�� ������ 0 �̻� 90�� �̸����� ����
    for(int i=1; i<=n; i++) arr[i] = arr[i] - ps;
    pe = pe - ps, ps = ps - ps;
    bool cx = (pe.x < 0), cy = (pe.y < 0);
    for(int i=1; i<=n; i++){
        if(cx) arr[i].x = -arr[i].x;
        if(cy) arr[i].y = -arr[i].y;
    }
    if(cx) pe.x = -pe.x;
    if(cy) pe.y = -pe.y;
    if(pe.x==0){
        for(int i=1; i<=n; i++) swap(arr[i].x, arr[i].y);
        swap(pe.x, pe.y);
    }
}

void putIntoGroup(){ /// groupList�� ����ֱ�
    for(int i=1; i<=n; i++){
        if(ccw(ps, pe, arr[i]) > 0) groupList[group[i]][0].push_back(i);
        else groupList[group[i]][1].push_back(i);
    }
}

struct dat{
    int x, y, w;
    dat(){}
    dat(int x, int y, int w): x(x), y(y), w(w){}
    bool operator<(const dat &r)const{
        return x<r.x;
    }
};

struct Fenwick{
    int n;
    int tree[40002];

    void init(int _n){
        n = _n;
        for(int i=0; i<=n; i++) tree[i] = 0;
    }

    void add(int x, int y){
        while(x<=n){
            tree[x] += y;
            x += x&-x;
        }
    }

    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }

    int sum(int l, int r){
        return sum(r) - sum(l-1);
    }
} tree;

map<pair<int, int>, int> mp;
int processQuery(int gx, int gy){
    if(mp.find(make_pair(gx, gy)) != mp.end()) return mp[make_pair(gx, gy)];
    int ret = 0;
    { /// 00 ó��
        vector<vector2> va, vb;
        for(int x: groupList[gx][0]) va.push_back(arr[x] - ps), vb.push_back(arr[x] - pe);
        for(int x: groupList[gy][0]) va.push_back(arr[x] - ps), vb.push_back(arr[x] - pe);
        sort(va.begin(), va.end());
        sort(vb.begin(), vb.end());
        vector<dat> vec;
        for(int x: groupList[gx][0]){
            vec.push_back(dat(lower_bound(va.begin(), va.end(), arr[x]-ps) - va.begin() + 1,
                              lower_bound(vb.begin(), vb.end(), arr[x]-pe) - vb.begin() + 1, 0));
        }
        for(int x: groupList[gy][0]){
            vec.push_back(dat(lower_bound(va.begin(), va.end(), arr[x]-ps) - va.begin() + 1,
                              lower_bound(vb.begin(), vb.end(), arr[x]-pe) - vb.begin() + 1, 1));
        }
        sort(vec.begin(), vec.end());
        tree.init((int)vec.size());
        for(dat tmp: vec){
            if(!tmp.w) ret += tree.sum(tmp.y, (int)vec.size());
            else tree.add(tmp.y, 1);
        }
    }

    { /// 11 ó��
        vector<vector2> va, vb;
        for(int x: groupList[gx][1]) va.push_back(arr[x] - ps), vb.push_back(arr[x] - pe);
        for(int x: groupList[gy][1]) va.push_back(arr[x] - ps), vb.push_back(arr[x] - pe);
        sort(va.begin(), va.end());
        sort(vb.begin(), vb.end());
        vector<dat> vec;
        for(int x: groupList[gx][1]){
            vec.push_back(dat(lower_bound(va.begin(), va.end(), arr[x]-ps) - va.begin() + 1,
                              lower_bound(vb.begin(), vb.end(), arr[x]-pe) - vb.begin() + 1, 0));
        }
        for(int x: groupList[gy][1]){
            vec.push_back(dat(lower_bound(va.begin(), va.end(), arr[x]-ps) - va.begin() + 1,
                              lower_bound(vb.begin(), vb.end(), arr[x]-pe) - vb.begin() + 1, 1));
        }
        for(dat &p: vec) swap(p.x, p.y);
        sort(vec.begin(), vec.end());
        tree.init((int)vec.size());
        for(dat tmp: vec){
            if(!tmp.w) ret += tree.sum(tmp.y, (int)vec.size());
            else tree.add(tmp.y, 1);
        }
    }

    { /// 01 ó��
        vector<vector2> psv, pev;
        for(int x: groupList[gy][1]) psv.push_back(arr[x] - ps), pev.push_back(arr[x] - pe);
        sort(psv.begin(), psv.end()), sort(pev.begin(), pev.end());
        for(int x: groupList[gx][0]){
            int A = lower_bound(psv.begin(), psv.end(), ps - arr[x]) - psv.begin();
            int B = pev.end() - lower_bound(pev.begin(), pev.end(), pe - arr[x]);
            ret += (int)psv.size() - A - B;
        }
    }

    { /// 10 ó��
        vector<vector2> psv, pev;
        for(int x: groupList[gy][0]) psv.push_back(arr[x] - ps), pev.push_back(arr[x] - pe);
        sort(psv.begin(), psv.end()), sort(pev.begin(), pev.end());
        for(int x: groupList[gx][1]){
            int A = psv.end() - lower_bound(psv.begin(), psv.end(), ps - arr[x]);
            int B = lower_bound(pev.begin(), pev.end(), pe - arr[x]) - pev.begin();
            ret += (int)psv.size() - A - B;
        }
    }

    return mp[make_pair(gx, gy)] = ret;
}

void processQueries(){
    for(int i=1; i<=q; i++){
        ans[i] = processQuery(query[i].x, query[i].y);
    }
}

void operate(){
    makePositive();
    putIntoGroup();
    processQueries();
    for(int i=1; i<=q; i++) printf("%d\n", ans[i]);
}

Compilation message

dragon2.cpp: In function 'void input()':
dragon2.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
dragon2.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%lld %lld %d", &arr[i].x, &arr[i].y, &group[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%lld %lld %lld %lld %d", &ps.x, &ps.y, &pe.x, &pe.y, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d %d", &query[i].x, &query[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1960 KB Output is correct
2 Correct 15 ms 1880 KB Output is correct
3 Correct 84 ms 2124 KB Output is correct
4 Correct 214 ms 9800 KB Output is correct
5 Correct 171 ms 9788 KB Output is correct
6 Correct 3 ms 2004 KB Output is correct
7 Correct 3 ms 2004 KB Output is correct
8 Correct 3 ms 1876 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3848 KB Output is correct
2 Correct 167 ms 3580 KB Output is correct
3 Correct 44 ms 3196 KB Output is correct
4 Correct 14 ms 3284 KB Output is correct
5 Correct 15 ms 3828 KB Output is correct
6 Correct 30 ms 4840 KB Output is correct
7 Correct 29 ms 4908 KB Output is correct
8 Correct 29 ms 4024 KB Output is correct
9 Correct 16 ms 3928 KB Output is correct
10 Correct 17 ms 3892 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1960 KB Output is correct
2 Correct 15 ms 1880 KB Output is correct
3 Correct 84 ms 2124 KB Output is correct
4 Correct 214 ms 9800 KB Output is correct
5 Correct 171 ms 9788 KB Output is correct
6 Correct 3 ms 2004 KB Output is correct
7 Correct 3 ms 2004 KB Output is correct
8 Correct 3 ms 1876 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 2 ms 1876 KB Output is correct
11 Correct 28 ms 3848 KB Output is correct
12 Correct 167 ms 3580 KB Output is correct
13 Correct 44 ms 3196 KB Output is correct
14 Correct 14 ms 3284 KB Output is correct
15 Correct 15 ms 3828 KB Output is correct
16 Correct 30 ms 4840 KB Output is correct
17 Correct 29 ms 4908 KB Output is correct
18 Correct 29 ms 4024 KB Output is correct
19 Correct 16 ms 3928 KB Output is correct
20 Correct 17 ms 3892 KB Output is correct
21 Correct 30 ms 4504 KB Output is correct
22 Correct 164 ms 3584 KB Output is correct
23 Correct 1200 ms 3684 KB Output is correct
24 Correct 1753 ms 11940 KB Output is correct
25 Correct 256 ms 12096 KB Output is correct
26 Correct 162 ms 12240 KB Output is correct
27 Correct 29 ms 5324 KB Output is correct
28 Correct 27 ms 5320 KB Output is correct
29 Execution timed out 4043 ms 6424 KB Time limit exceeded
30 Halted 0 ms 0 KB -