oj.uz

Submission #102107

# Submission time Handle Problem Language Result Execution time Memory
102107 2019-03-22T11:39:46 Z forestryks Dragon 2 (JOI17_dragon2) C++14
15 / 100
 4000 ms 8340 KB 
///////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout)
#define f first
#define s second
#define x1 x1qwer
#define y1 y1qwer
#define right right123
#define left left123
#define foreach(it, v) for (auto it : v)
#define rep(it, n) for (int it = 0; it < n; ++it)
#define forin(it, l, r) for (int it = l; it < r; ++it)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double DINF = numeric_limits<double>::infinity();
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw_(MOD);
uniform_int_distribution<ll> rd_;
ll randomll() { return rd_(mmtw_);}
ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; }
////////////////////////////////////////////////////////////////////////////////////////////////

struct pt {
    ld x, y;
};

ld dot(const pt &a, const pt &b) {
    return a.x * b.x + a.y * b.y;
}

ld cross(const pt &a, const pt &b) {
    return a.x * b.y - a.y * b.x;
}

pt operator-(const pt &a, const pt &b) {
    return {a.x - b.x, a.y - b.y};
}

ld ang(const pt &a, const pt &b) {
    return atan2(cross(a, b), dot(a, b));
}

const int MAXN = 1e5 + 5;
int n, m;
pt a[MAXN];
int c[MAXN];
vector<int> ids[MAXN];
vector<pair<int, int>> q[MAXN];
pt A, B;
ld Ap[MAXN], Bp[MAXN], pA[MAXN], pB[MAXN];
int ans[MAXN];
int cnt[MAXN];
bool on_left[MAXN];

void solve() {
    rep(i, n) {
        pt p = a[i];

        if (cross(p - A, B - A) < 0) {
            on_left[i] = true;
            Bp[i] = ang(B - A, p - A);
            Ap[i] = ang(B - A, p - B);

            pA[i] = ang(B - A, A - p);
            pB[i] = ang(B - A, B - p);
        } else {
            Ap[i] = ang(B - A, p - A);
            Bp[i] = ang(B - A, p - B);

            pB[i] = ang(B - A, A - p);
            pA[i] = ang(B - A, B - p);
        }

        // Ap[i] = ang(p - A, B - A);
        // Bp[i] = ang(p - B, B - A);
        // pA[i] = ang(A - p, B - A);
        // pB[i] = ang(B - p, B - A);
        // 

        // Ap[i] = ang(B - A, p - A);
        // Bp[i] = ang(B - A, p - B);
        // pA[i] = ang(B - A, A - p);
        // pB[i] = ang(B - A, B - p);
        // if (Ap[i] > Bp[i]) swap(Ap[i], Bp[i]);
        // if (pA[i] > pB[i]) swap(pA[i], pB[i]);

        // if (cross(p - A, B - A) < 0) on_left[i] = true;
    }

    // rep(i, n) {
    //     cout << Ap[i] << ' ' << Bp[i] << ' ' << pA[i] << ' ' << pB[i] << endl;
    // }

    for (int gr = 0; gr < m; ++gr) {
        memset(cnt, 0, sizeof(int) * m);
        for (auto i : ids[gr]) {
            for (int j = 0; j < n; ++j) {
                // if (i != 2 || j != 1) continue;

                // cout << on_left[i] << ' ' << Ap[i] << ' ' << Bp[i] << ' ' << pA[i] << ' ' << pB[i] << endl;
                // cout << on_left[j] << ' ' << Ap[j] << ' ' << Bp[j] << ' ' << pA[j] << ' ' << pB[j] << endl;

                if (on_left[i] == on_left[j]) {
                    cnt[c[j]] += (pA[j] <= pA[i] && pB[i] <= pB[j]);
                } else {
                    cnt[c[j]] += (pA[i] <= Ap[j] && Bp[j] <= pB[i]);
                }

                // cnt[c[j]] += (pA[i] < Ap[j] && Bp[j] < pB[i]);
            }
        }

        for (auto &it : q[gr]) {
            ans[it.s] = cnt[it.f];
        }
    }

    // rep(i, n) {
    //     cout << a[i].x << ' ' << a[i].y << " : " << Ap[i] << endl;
    // }
}

int main() {
    FAST_IO;
    cout.precision(10);
    cout.setf(ios::fixed);

    // while (true) {
    //     pt a, b;
    //     cin >> a.x >> a.y;
    //     b = {1, 0};
    //     cout << ang(b, a) << endl;
    // }

    // return 0;

    cin >> n >> m;

    rep(i, n) {
        cin >> a[i].x >> a[i].y >> c[i];
        c[i]--;
        ids[c[i]].push_back(i);
    }

    cin >> A.x >> A.y >> B.x >> B.y;

    int qc;
    cin >> qc;
    rep(i, qc) {
        int f, s;
        cin >> f >> s;
        f--; s--;
        q[f].push_back({s, i});
    }

    solve();

    rep(i, qc) {
        cout << ans[i] << '\n';
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5376 KB Output is correct
2 Correct 82 ms 5496 KB Output is correct
3 Correct 97 ms 5624 KB Output is correct
4 Correct 124 ms 7160 KB Output is correct
5 Correct 116 ms 7436 KB Output is correct
6 Correct 57 ms 5504 KB Output is correct
7 Correct 67 ms 5632 KB Output is correct
8 Correct 96 ms 5648 KB Output is correct
9 Correct 48 ms 5504 KB Output is correct
10 Correct 43 ms 5504 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4096 ms 8340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5376 KB Output is correct
2 Correct 82 ms 5496 KB Output is correct
3 Correct 97 ms 5624 KB Output is correct
4 Correct 124 ms 7160 KB Output is correct
5 Correct 116 ms 7436 KB Output is correct
6 Correct 57 ms 5504 KB Output is correct
7 Correct 67 ms 5632 KB Output is correct
8 Correct 96 ms 5648 KB Output is correct
9 Correct 48 ms 5504 KB Output is correct
10 Correct 43 ms 5504 KB Output is correct
11 Execution timed out 4096 ms 8340 KB Time limit exceeded
12 Halted 0 ms 0 KB -