QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#444409#8525. Mercenariesucup-team3926#WA 477ms68508kbC++2011.2kb2024-06-15 18:54:102024-06-15 18:54:12

Judging History

你现在查看的是最新测评结果

  • [2024-06-15 18:54:12]
  • 评测
  • 测评结果:WA
  • 用时:477ms
  • 内存:68508kb
  • [2024-06-15 18:54:10]
  • 提交

answer

// !!!!!!
// rename to template.cpp instead of main.cpp
#include <bits/stdc++.h>

#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
                    .time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
template<typename T, typename U>
ostream& operator << (ostream& o, const pair<T, U>& p) {
    return o << "(" << p.first << ", " << p.second << ")";
}
template<typename T>
ostream& operator << (ostream& o, const vector<T>& v) {
    bool first = true;
    o << "[";
    for (const auto& l : v) {
        if (!first) o << ", ";
        o << l;
        first = false;
    }
    return o << "]";
}
template<typename T>
ostream& operator << (ostream& o, const set<T>& v) {
    bool first = true;
    o << "{";
    for (const auto& l : v) {
        if (!first) o << ", ";
        o << l;
        first = false;
    }
    return o << "}";
}
#ifdef ONPC
#define show(x) cout << "LINE " << __LINE__ << ": " << #x << "=" << x << std::endl;
#else
#define show(x) 42
#endif

using ll = long long;
using ld = double;

// _________ vect (2D) ______________
template <typename T>
struct vect {
    T x = 0;
    T y = 0;

    vect() = default;
    vect(T x_, T y_) : x(x_), y(y_) {}

    inline T len2() const {
        return x * x + y * y;
    }

    inline ld len() const {
        return sqrtl(len2());
    }

    inline void rotate() {
        swap(x, y);
        y = -y;
    }
};

template <typename T>
inline istream& operator>>(istream& in, vect<T>& v) {
    return in >> v.x >> v.y;
}

template <typename T>
inline ostream& operator<<(ostream& out, const vect<T>& v) {
    return out << "[" << v.x << "," << v.y << "]";
}

template <typename T>
inline vect<T> operator+(const vect<T>& a, const vect<T>& b) {
    return vect<T>(a.x + b.x, a.y + b.y);
}

template <typename T>
inline vect<T> operator-(const vect<T>& a, const vect<T>& b) {
    return vect<T>(a.x - b.x, a.y - b.y);
}

template <typename T>
inline vect<T> operator*(const vect<T>& a, T k) {
    return vect<T>(a.x * k, a.y * k);
}

template <typename T>
inline T operator*(const vect<T>& a, const vect<T>& b) {
    return a.x * b.x + a.y * b.y;
}

template <typename T>
inline T operator^(const vect<T>& a, const vect<T>& b) {
    return a.x * b.y - a.y * b.x;
}

template <typename T>
bool operator==(const vect<T>& a, const vect<T>& b) {
    return a.x == b.x && a.y == b.y;
}

template <typename T>
bool operator<(const vect<T>& a, const vect<T>& b) {
    return (a ^ b) > 0;
}

void convexHull(vector<vect<ll>>& v) {
    if (v.empty()) return;
    sort(v.begin(), v.end(), [&](const auto& v1, const auto& v2) {
        return tie(v1.x, v1.y) < tie(v2.x, v2.y);
    });
    v.resize(unique(v.begin(), v.end()) - v.begin());
    if (v.size() == 1) return;
    vector<vect<ll>> st;
    st.reserve(v.size() + 1);
    for (int order = 0; order < 2; order++) {
        int sz = order == 1 ? st.size() : 1;
        for (const auto &vc: v) {
            while (st.size() > sz) {
                if (((st.back() - st.end()[-2]) ^ (vc - st.back())) > 0) break;
                st.pop_back();
            }
            st.emplace_back(vc);
        }
        reverse(v.begin(), v.end());
    }
    if (st.size() > 1) st.pop_back();
    swap(v, st);
}

int n;
vector<vect<ll>> initial_lines;
vector<vector<vect<ll>>> curve;
vector<tuple<vect<ll>, int, int>> events;
vector<int> pos;

vector<int> v;
vector<vect<ll>> qv;
vector<ll> c;
vector<int> ans;

vector<vect<ll>> l1, l2;

const int T = (1 << 19) + 239;
const vect<ll> vINF = vect<ll>(-1, 1);

vect<ll> sufl[T];
vect<ll> add[T];
vect<ll> best[T];
vect<ll> ub[T];
vect<ll> global_t;

void push(int i, int l, int r) {
    if (add[i].x == 0 && add[i].y == 0) return;
    best[i] = best[i] + add[i];
    sufl[i] = sufl[i] + add[i];
    if (r - l > 1) {
        add[2 * i + 1] = add[2 * i + 1] + add[i];
        add[2 * i + 2] = add[2 * i + 2] + add[i];
    }
    add[i] = vect<ll>(0, 0);
}

void merge(int i) {
    ub[i] = min(ub[2 * i + 1], ub[2 * i + 2]);
    vect v1 = best[2 * i + 1];
    vect v2 = best[2 * i + 2];
    if (make_pair((v1 * global_t), (global_t ^ v1)) < make_pair((v2 * global_t), (global_t ^ v2))) {
        swap(v1, v2);
    }
    best[i] = v1;
    auto vc = v2 - v1;
    vc.rotate();
    if (vc.x != 0 || vc.y != 0) {
        if (vc.x >= 0 && vc.y >= 0) {
            if ((global_t ^ vc) <= 0) {
                cerr << (global_t ^ vc) << "\n";
                cerr << global_t << " " << v1 << " " << v2 << " " << vc << "\n";
            }
            assert((global_t ^ vc) > 0);
            ub[i] = min(ub[i], vc);
        }
    }
}

void build(int i, int l, int r) {
    add[i] = vect<ll>(0, 0);
    if (r - l == 1) {
        sufl[i] = l2[l];
        best[i] = l1[l];
        ub[i] = vINF;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * i + 1, l, mid);
    build(2 * i + 2, mid, r);
    merge(i);
}

void upd(int i, int l, int r, int ql, int qr, const vect<ll>& delta) {
    push(i, l, r);
    if (qr <= l || r <= ql) return;
    if (ql <= l && r <= qr) {
        add[i] = add[i] + delta;
        push(i, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * i + 1, l, mid, ql, qr, delta);
    upd(2 * i + 2, mid, r, ql, qr, delta);
    merge(i);
}

void dfs(int i, int l, int r) {
    push(i, l, r);
    if ((global_t ^ ub[i]) > 0) return;
    int mid = (l + r) / 2;
    dfs(2 * i + 1, l, mid);
    dfs(2 * i + 2, mid, r);
    merge(i);
}

void move_global(const vect<ll>& new_global) {
    if ((global_t ^ new_global) == 0) {
        global_t = new_global;
        return;
    }
    global_t = new_global;
    dfs(0, 0, n);
}

vect<ll> getline(int i, int l, int r, int x) {
    push(i, l, r);
    if (r - l == 1) {
        return sufl[i];
    }
    int mid = (l + r) / 2;
    vect<ll> res;
    if (x < mid) {
        res = getline(2 * i + 1, l, mid, x);
        push(2 * i + 2, mid, r);
    } else {
        res = getline(2 * i + 2, mid, r, x);
        push(2 * i + 1, l, mid);
    }
    merge(i);
    return res;
}

/*int getans(int i, int l, int r, int ql, int qr, ll lb, bool req) {
    push(i, l, r);
    if (qr <= l || r <= ql) return -1;
    int mid = (l + r) / 2;
    if (ql <= l && r <= qr) {
        if ((best[i] * global_t) < lb) return -1;
        if (r - l == 1) return l;
        if (!req) return -1;
        int res;
        if ((best[2 * i + 2] * global_t) < lb) {
            res = getans(2 * i + 1, l, mid, ql, qr, lb, true);
            push(2 * i + 2, mid, r);
        } else {
            res = getans(2 * i + 2, mid, r, ql, qr, lb, true);
            push(2 * i + 1, l, mid);
        }
        merge(i);
        return res;
    }
    int res = getans(2 * i + 2, mid, r, ql, qr, lb, req);
    if (res != -1 || !req) {
        getans(2 * i + 1, l, mid, ql, qr, lb, false);
        merge(i);
        return res;
    }
    res = getans(2 * i + 1, l, mid, ql, qr, lb, true);
    merge(i);
    return res;
}*/

int getans(int i, int l, int r, int ql, int qr, ll lb) {
    push(i, l, r);
    if (qr <= l || r <= ql) return -1;
    int mid = (l + r) / 2;
    if (ql <= l && r <= qr) {
        //cerr << i << " " << l << " " << r << " " << best[i] << "\n";
        //cerr << lb << "\n";
        //cerr << global_t << "\n";
        if ((best[i] * global_t) < lb) return -1;
        if (r - l == 1) return l;
        int res;
        if ((best[2 * i + 2] * global_t) < lb) {
            res = getans(2 * i + 1, l, mid, ql, qr, lb);
            push(2 * i + 2, mid, r);
        } else {
            res = getans(2 * i + 2, mid, r, ql, qr, lb);
            push(2 * i + 1, l, mid);
        }
        merge(i);
        return res;
    }
    int res = getans(2 * i + 2, mid, r, ql, qr, lb);
    if (res != -1) return res;
    return getans(2 * i + 1, l, mid, ql, qr, lb);
}

void solve() {
    cin >> n;
    initial_lines.resize(n);
    curve.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> initial_lines[i];
        if (i + 1 < n) {
            int sz;
            cin >> sz;
            vector<vect<ll>> pt;
            for (int j = 0; j < sz; j++) {
                vect<ll> cur;
                cin >> cur;
                if (cur.x == 0 && cur.y == 0) continue;
                pt.emplace_back(cur);
            }
            if (!pt.empty()) {
                convexHull(pt);
                int l = 0;
                for (int j = 0; j < (int)pt.size(); j++) {
                    if (make_pair(pt[j].x, pt[j].y) > make_pair(pt[l].x, pt[l].y)) {
                        l = j;
                    }
                }
                int r = 0;
                for (int j = 0; j < (int)pt.size(); j++) {
                    if (make_pair(pt[j].y, pt[j].x) > make_pair(pt[r].y, pt[r].x)) {
                        r = j;
                    }
                }
                vector<vect<ll>> new_pt;
                while (l != r) {
                    new_pt.emplace_back(pt[l]);
                    l = (l + 1) % pt.size();
                }
                new_pt.emplace_back(pt[r]);
                swap(pt, new_pt);
            }
            curve[i] = pt;
        }
        if (curve[i].empty()) {
            curve[i].emplace_back(0, 0);
        }
        //show(curve[i]);
        for (int t = 0; t < (int)curve[i].size() - 1; t++) {
            auto vc(curve[i][t + 1] - curve[i][t]);
            vc.rotate();
            events.emplace_back(vc, 0, i);
        }
    }

    int q;
    cin >> q;
    v.resize(q);
    qv.resize(q);
    c.resize(q);
    ans.resize(q, -1);
    for (int i = 0; i < q; i++) {
        cin >> v[i] >> qv[i] >> c[i];
        v[i]--;
        events.emplace_back(qv[i], 1, i);
    }

    sort(events.begin(), events.end());

    pos.resize(n, 0);
    l2.resize(n);
    for (int i = 0; i < n; i++) {
        l2[i] = curve[i][pos[i]];
    }
    for (int i = n - 2; i >= 0; i--) {
        l2[i] = l2[i] + l2[i + 1];
    }
    l1.resize(n);
    for (int i = 0; i < n; i++) {
        l1[i] = l2[i] + initial_lines[i];
    }

    global_t = vect<ll>(1, 0);
    build(0, 0, n);

    for (auto [dir, type, i] : events) {
        move_global(dir);
        if (type == 0) {
            auto delta = curve[i][pos[i] + 1] - curve[i][pos[i]];
            pos[i]++;
            upd(0, 0, n, 0, i + 1, delta);
        } else {
            auto lc = getline(0, 0, n, v[i]);
            c[i] += (lc * qv[i]);
            ans[i] = getans(0, 0, n, 0, v[i] + 1, c[i]);
        }
    }

    for (int i = 0; i < q; i++) {
        if (ans[i] == -1) {
            cout << ans[i] << "\n";
        } else {
            cout << ans[i] + 1 << "\n";
        }
    }
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed << setprecision(20);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    cerr << "\n\nConsumed " << TIME << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 10076kb

input:

3
1 1
2 1 2 1 2
3 2
5 1 5 4 3 3 4 5 1 1 2
4 5
12
1 1 1 1
2 1 1 1
3 1 1 1
3 1 1 9
3 2 2 20
3 1 2 18
3 1 2 19
3 1 2 20
3 0 1 8
2 1 0 4
2 1 0 3
2 1 0 2

output:

1
2
3
3
2
2
1
-1
1
-1
2
2

result:

ok 12 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 10036kb

input:

2
47 11
1 98 25
9 90
10
1 32 28 1811
2 17 44 4114
1 36 88 2661
2 79 33 3681
1 53 26 2778
2 59 20 2332
2 63 45 4616
2 72 11 10835
1 13 28 919
2 16 59 4445

output:

1
-1
-1
2
-1
1
2
1
1
2

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 10208kb

input:

3
87 42
5 69 12 82 79 10 88 45 51 40 3
18 6
5 73 100 58 41 40 88 54 5 40 98
31 63
100
3 32 13 1811
1 51 21 5318
1 32 5 2994
2 77 51 19184
2 78 60 1763
1 10 1 913
1 22 51 4057
1 2 5 385
2 50 15 989
2 65 53 1488
1 49 82 7708
2 33 90 1133
1 23 33 3388
1 92 36 9516
3 39 61 10014
2 43 55 1103
2 48 38 127...

output:

3
1
1
1
2
-1
-1
-1
2
2
-1
2
-1
1
2
2
-1
3
2
2
3
1
1
1
-1
1
1
1
3
1
-1
1
-1
1
2
1
2
1
1
1
1
1
-1
1
-1
-1
1
1
-1
-1
1
1
2
1
1
-1
2
-1
1
1
1
1
3
1
2
3
2
2
1
1
-1
1
1
3
1
1
1
3
2
1
1
2
1
2
1
2
1
-1
-1
-1
1
2
1
1
-1
-1
1
3
2
2

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 209ms
memory: 28280kb

input:

2
309248041 338995438
500000 1235 4866 1931 3652 1921 258 545 587 3001 542 3074 1694 4944 206 3217 3135 2388 4791 1890 3281 3840 4614 4491 1339 4660 1708 2225 3199 736 1306 4175 4652 906 3509 2571 1578 50 981 402 4975 2730 2198 4546 3120 40 815 2492 518 2102 2651 1018 3996 1764 808 3934 4312 1981 40...

output:

2
1
-1
2
2
2
1
1
2
-1
2
2
1
1
2
1
2
2
1
2
2
1
-1
-1
1
-1
2
-1
1
2
1
1
1
1
-1
1
-1
-1
-1
1
2
2
1
1
1
2
-1
-1
1
-1
1
2
-1
1
2
1
2
2
-1
2
1
2
2
-1
2
2
-1
2
1
2
1
-1
-1
1
1
-1
2
1
2
2
1
1
1
1
2
2
-1
-1
1
2
2
-1
2
-1
-1
-1
1
2
1
1
2
2
1
-1
-1
2
2
2
1
-1
1
2
2
-1
1
-1
-1
-1
1
2
1
2
1
-1
-1
1
2
2
-1
2
2
2
...

result:

ok 200000 numbers

Test #5:

score: 0
Accepted
time: 477ms
memory: 68508kb

input:

200000
999999511 993051669
2 5000 5000 5000 5000
1000000000 1000000000
3 5000 5000 5000 5000 5000 5000
995868520 999999999
2 5000 5000 5000 5000
660478427 999992996
3 5000 5000 5000 5000 5000 5000
999999979 999999998
2 5000 5000 5000 5000
861450412 989532141
3 5000 5000 5000 5000 5000 5000
949861679...

output:

145800
198491
112658
29436
38091
122582
7727
87686
192036
97288
60184
836
39235
158331
121422
117149
189664
153018
181334
56603
69911
173097
165342
124250
103223
110099
177817
11459
37052
28918
57236
143793
19234
10313
75590
6597
18202
176357
102394
179685
5171
162359
72023
56758
88764
17257
100583
...

result:

ok 200000 numbers

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 10040kb

input:

20
1538 3628
4 2423 3790 3127 3961 2614 3582 2016 4789
1441 276
3 2518 253 4221 265 3236 2574
1668 3370
4 4489 3533 4501 2177 1067 2337 2765 1480
1179 1926
3 4922 2537 1477 653 325 444
3964 2924
2 3415 4463 822 3257
210 4068
2 1969 167 1978 3712
2067 540
4 1560 2211 4050 4196 442 2279 442 2448
2962 ...

output:

5
14
5
1
2
3
6
-1
8
6
2
11
1
8
8
3
3
13
4
5

result:

wrong answer 10th numbers differ - expected: '7', found: '6'