oj.uz

Submission #594940

# Submission time Handle Problem Language Result Execution time Memory
594940 2022-07-13T07:30:28 Z 반딧불(#8437) Dragon 2 (JOI17_dragon2) C++17
60 / 100
 4000 ms 6624 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;

int processQuery(int gx, int 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 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 4 ms 1876 KB Output is correct
2 Correct 15 ms 1876 KB Output is correct
3 Correct 110 ms 1884 KB Output is correct
4 Correct 163 ms 3560 KB Output is correct
5 Correct 79 ms 3548 KB Output is correct
6 Correct 7 ms 1876 KB Output is correct
7 Correct 6 ms 1876 KB Output is correct
8 Correct 5 ms 1876 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 3 ms 1876 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3840 KB Output is correct
2 Correct 177 ms 2928 KB Output is correct
3 Correct 37 ms 2900 KB Output is correct
4 Correct 21 ms 2900 KB Output is correct
5 Correct 15 ms 3404 KB Output is correct
6 Correct 32 ms 4584 KB Output is correct
7 Correct 41 ms 4540 KB Output is correct
8 Correct 41 ms 3716 KB Output is correct
9 Correct 21 ms 3872 KB Output is correct
10 Correct 19 ms 3788 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 15 ms 1876 KB Output is correct
3 Correct 110 ms 1884 KB Output is correct
4 Correct 163 ms 3560 KB Output is correct
5 Correct 79 ms 3548 KB Output is correct
6 Correct 7 ms 1876 KB Output is correct
7 Correct 6 ms 1876 KB Output is correct
8 Correct 5 ms 1876 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 3 ms 1876 KB Output is correct
11 Correct 36 ms 3840 KB Output is correct
12 Correct 177 ms 2928 KB Output is correct
13 Correct 37 ms 2900 KB Output is correct
14 Correct 21 ms 2900 KB Output is correct
15 Correct 15 ms 3404 KB Output is correct
16 Correct 32 ms 4584 KB Output is correct
17 Correct 41 ms 4540 KB Output is correct
18 Correct 41 ms 3716 KB Output is correct
19 Correct 21 ms 3872 KB Output is correct
20 Correct 19 ms 3788 KB Output is correct
21 Correct 35 ms 4264 KB Output is correct
22 Correct 183 ms 3336 KB Output is correct
23 Correct 1183 ms 3080 KB Output is correct
24 Correct 1650 ms 6008 KB Output is correct
25 Correct 183 ms 6192 KB Output is correct
26 Correct 83 ms 6572 KB Output is correct
27 Correct 21 ms 4408 KB Output is correct
28 Correct 23 ms 4356 KB Output is correct
29 Execution timed out 4077 ms 6624 KB Time limit exceeded
30 Halted 0 ms 0 KB -