#118432 (C++14) No.202 1円玉投げ

• 問題: No.202 1円玉投げ
• ユーザー: izuru_matsuura
• 提出日時: 2016-09-22 22:05:24
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 3,951 bytes
• コンパイル時間: 2,177 ms
• コンパイル使用メモリ: 180,024 KB
• 実行使用メモリ: 81,056 KB
• 最終ジャッジ日時: 2024-12-22 10:29:06
• 合計ジャッジ時間: 7,413 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	175 ms; 80,368 KB
testcase_01	AC	210 ms; 81,056 KB
testcase_02	AC	2 ms; 6,820 KB
testcase_03	AC	2 ms; 6,816 KB
testcase_04	AC	2 ms; 6,816 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	224 ms; 80,368 KB
testcase_17	AC	179 ms; 80,364 KB
testcase_18	AC	179 ms; 80,360 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	4 ms; 6,820 KB
testcase_23	AC	3 ms; 6,816 KB
testcase_24	AC	4 ms; 6,820 KB
testcase_25	WA	-
testcase_26	AC	4 ms; 6,816 KB
testcase_27	AC	4 ms; 6,816 KB
testcase_28	AC	4 ms; 6,820 KB
testcase_29	AC	4 ms; 6,820 KB
testcase_30	AC	3 ms; 6,820 KB
testcase_31	AC	9 ms; 6,816 KB
testcase_32	WA	-
testcase_33	WA	-
testcase_34	AC	4 ms; 6,816 KB
testcase_35	AC	443 ms; 80,360 KB
testcase_36	AC	169 ms; 80,364 KB
testcase_37	WA	-
testcase_38	AC	455 ms; 80,364 KB
testcase_39	AC	2 ms; 6,820 KB
testcase_40	WA	-

ソースコード

#include <bits/stdc++.h>

#define whole(xs) xs.begin(),xs.end()

using namespace std;

namespace {

    typedef double real;
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        auto i = vs.begin();
        os << "[" << *i;
        for (++i; i != vs.end(); ++i) os << " " << *i;
        return os << "]";
    }
    template<class T> istream& operator>>(istream& is, vector<T>& vs) {
        for (auto it = vs.begin(); it != vs.end(); it++) is >> *it;
        return is;
    }

    struct Point {
        ll x, y;
        int id;
        Point() {}
        Point(ll x, ll y) : x(x), y(y) {}
        static bool compY(const Point& a, const Point& b) {
            return a.y == b.y ? a.x < b.x : a.y < b.y;
        }
    };
    istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }
    struct Node {
        Node* parent;
        shared_ptr<Node> left, right;
        ll left_x, right_x;
        vector<Point> ys;
    };
    //ostream& operator<<(ostream& os, const Node& node) {
    //    return os << "( [" << node.left_x << "," << node.right_x << "] -> " << node.ys;
    //}
    shared_ptr<Node> construct(vector<Point>::iterator lb, vector<Point>::iterator ub) {
        auto n = make_shared<Node>();
        n->left_x = lb->x;
        n->right_x = (ub - 1)->x;
        if (ub - lb == 1) {
            n->ys.clear(); n->ys.push_back(*lb);
            return n;
        }
        auto mid = lb + (ub - lb) / 2;
        auto l = construct(lb, mid),
             r = construct(mid, ub);
        l->parent = n.get();
        r->parent = n.get();
        n->left = l;
        n->right = r;
        size_t li = 0, ri = 0;
        while (true) {
            if (li >= l->ys.size() && ri >= r->ys.size()) break;
            if (li >= l->ys.size()) n->ys.push_back(r->ys[ri++]);
            else if (ri >= r->ys.size()) n->ys.push_back(l->ys[li++]);
            else {
                n->ys.push_back( l->ys[li].y < r->ys[ri].y ? l->ys[li++] : r->ys[ri++] );
            }
        }
        return n;
    }

    /* (sx <= x <= gx && sy <= y <= gy)縺ｪ繧狗せ(x, y)繧池esult縺ｫ蜈･繧後ｋ. 髢牙玄髢薙↑縺ｮ豕ｨ諢・*/
    void query(shared_ptr<Node> root, ll sx, ll sy, ll gx, ll gy, vector<Point>& result) {
        if (gx < root->left_x || root->right_x < sx) {
            // do nothing;
        } else if (sx <= root->left_x && root->right_x <= gx) {
            auto& ys = root->ys;
            auto lb = upper_bound(whole(ys), Point(0, sy - 1), Point::compY);
            auto ub = lower_bound(whole(ys), Point(0, gy + 1), Point::compY);
            result.insert(result.end(), lb, ub);
        } else {
            query(root->left, sx, sy, gx, gy, result);
            query(root->right, sx, sy, gx, gy, result);
        }
    }

    int N;
    vector<Point> P;
    void input() {
        cin >> N;
        P.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> P[i]; P[i].id = i;
        }
    }

    ll dist2(const Point& a, const Point& b) {
        ll dx = a.x - b.x;
        ll dy = a.y - b.y;
        return dx * dx + dy * dy;
    }

    void solve() {
        auto root = construct(P.begin(), P.end());
        int ans = 0;
        vector<bool> used(N, false);
        for (int i = 0; i < N; i++) {
            ll x = P[i].x;
            ll y = P[i].y;
            vector<Point> res;
            query(root, x - 20, y - 20, x + 20, y + 20, res);
            bool flag = false;
            for (auto p : res) {
                if (dist2(P[i], p) >= 400) continue;
                if (not used[p.id]) continue;
                flag = true;
                break;
            }
            if (not flag) {
                used[i] = true;
                ans++;
            }
        }
        cout << ans << endl;
    }
}

int main() {
    input(); solve();
    return 0;
}