QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#625047#9427. Collect the CoinsffaoTL 0ms3616kbC++232.7kb2024-10-09 17:15:572024-10-09 17:15:57

Judging History

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

  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-09 17:15:57]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3616kb
  • [2024-10-09 17:15:57]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int maxn = 1e6 + 100;

ll n;
pair<ll, ll> vec[maxn];

bool check(ll V) {
    vector<int> dp(n + 1);
    multiset<pair<ll, ll>> all;

    auto valid = [&](ll i, ll j) {
        auto [t1, p1] = vec[i];
        auto [t2, p2] = vec[j];
        return abs(p1 - p2) <= abs(t1 - t2) * V;
    };

    auto insert = [&](ll pos) {
        auto [t, p] = vec[pos];
        // insert (p - tV, -p-tV)
        // ...
        auto x = p - t * V;
        auto y = -p - t * V;
        while (all.size()) {
            auto it = all.lower_bound({x + 1, -3e18});
            if (it == all.begin()) break;
            auto [tx, ty] = *(--it);
            if (ty <= y) all.extract({tx, ty});
        }

        bool flag = true;
        if (all.size()) {
            auto rit = all.lower_bound({x, y});
            if (rit == all.end())
                flag = true;
            else {
                auto [tx, ty] = *rit;
                if (ty < y)
                    flag = true;
                else
                    flag = false;
            }
        }
        if (flag) all.insert({x, y});
    };

    for (int i = 2; i < n; i++) {
        if (!valid(i - 1, i)) break;
        dp[i + 1] = true;
    }
    // check st = 2, i = 3?
    dp[2] = true;
    for (ll i = 3; i <= n; i++) {
        if (!valid(i - 2, i - 1)) {
            all.clear();
        }
        // cout << "addr2" << endl;
        if (dp[i - 1]) insert(i - 2);
        // j-1
        auto [qt, qp] = vec[i];
        auto qx = qp - qt * V;
        auto qy = -qp - qt * V;
        auto it = all.lower_bound({qx, qy});
        if (it != all.end()) {
            auto [tx, ty] = *it;
            if (ty >= qy) dp[i] = true;
        }
    }
    for (int temp = n; temp >= 1; temp--) {
        if (temp < n and !valid(temp, temp + 1)) break;
        if (dp[temp]) return true;
    }
    return false;
};

void solve() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> vec[i].first >> vec[i].second;
    }
    unordered_set<ll> all_pos;
    for (ll i = 1; i <= n; i++) {
        all_pos.insert(vec[i].second);
    }
    if (all_pos.size() <= 2) {
        cout << 0 << '\n';
        return;
    }

    ll L = 1, R = 1e9 + 100;
    while (L < R) {
        ll mid = (L + R) / 2;
        if (check(mid))
            R = mid;
        else
            L = mid + 1;
    }
    if (L > 1e9) L = -1;
    cout << L << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

3
5
1 1
3 7
3 4
4 3
5 10
1
10 100
3
10 100
10 1000
10 10000

output:

2
0
-1

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

1135
2
6 5
8 8
8
2 9
2 10
4 4
5 3
6 2
6 8
8 2
8 7
1
9 1
6
4 6
6 1
6 2
9 10
10 1
10 7
5
1 6
2 5
6 7
8 6
10 3
8
1 10
5 4
5 7
6 1
6 6
8 4
9 1
9 4
8
1 1
1 3
2 9
3 3
5 9
6 10
9 7
10 7
3
5 8
6 6
10 6
7
2 9
4 7
5 10
6 3
6 7
8 9
10 1
6
1 4
2 8
5 9
7 10
9 1
10 5
9
2 7
4 5
5 9
6 10
7 4
9 4
9 9
10 3
10 7
1
3 1...

output:


result: