結果

問題 No.202 1円玉投げ
ユーザー izuru_matsuuraizuru_matsuura
提出日時 2016-09-22 22:30:50
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 476 ms / 5,000 ms
コード長 4,209 bytes
コンパイル時間 1,994 ms
コンパイル使用メモリ 180,536 KB
実行使用メモリ 83,512 KB
最終ジャッジ日時 2023-08-23 23:26:33
合計ジャッジ時間 10,032 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 311 ms
83,512 KB
testcase_01 AC 454 ms
82,184 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 15 ms
7,256 KB
testcase_06 AC 401 ms
72,420 KB
testcase_07 AC 459 ms
78,388 KB
testcase_08 AC 443 ms
79,248 KB
testcase_09 AC 205 ms
42,656 KB
testcase_10 AC 68 ms
20,336 KB
testcase_11 AC 161 ms
37,744 KB
testcase_12 AC 172 ms
38,520 KB
testcase_13 AC 76 ms
21,460 KB
testcase_14 AC 17 ms
7,800 KB
testcase_15 AC 195 ms
41,736 KB
testcase_16 AC 209 ms
82,784 KB
testcase_17 AC 392 ms
82,592 KB
testcase_18 AC 395 ms
82,804 KB
testcase_19 AC 186 ms
40,196 KB
testcase_20 AC 335 ms
67,012 KB
testcase_21 AC 174 ms
39,908 KB
testcase_22 AC 4 ms
4,380 KB
testcase_23 AC 3 ms
4,376 KB
testcase_24 AC 4 ms
4,380 KB
testcase_25 AC 4 ms
4,376 KB
testcase_26 AC 3 ms
4,380 KB
testcase_27 AC 3 ms
4,376 KB
testcase_28 AC 3 ms
4,380 KB
testcase_29 AC 4 ms
4,376 KB
testcase_30 AC 3 ms
4,376 KB
testcase_31 AC 5 ms
4,376 KB
testcase_32 AC 3 ms
4,380 KB
testcase_33 AC 3 ms
4,380 KB
testcase_34 AC 4 ms
4,376 KB
testcase_35 AC 305 ms
82,648 KB
testcase_36 AC 302 ms
82,628 KB
testcase_37 AC 476 ms
82,588 KB
testcase_38 AC 310 ms
82,792 KB
testcase_39 AC 2 ms
4,380 KB
testcase_40 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 compX(const Point& a, const Point& b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
        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; }
    ostream& operator<<(ostream& os, const Point& p) { return os << "Point(" << 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() {
        vector<Point> Q = P;
        sort(Q.begin(), Q.end(), Point::compX);
        auto root = construct(Q.begin(), Q.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;
}
0