/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 2ms 532.0 KiB
#3 Accepted 2ms 532.0 KiB
#4 Accepted 3ms 600.0 KiB
#5 Accepted 100ms 632.0 KiB
#6 Accepted 103ms 624.0 KiB
#7 Accepted 84ms 1.098 MiB
#8 Accepted 873ms 86.383 MiB
#9 Accepted 534ms 17.742 MiB
#10 Accepted 27ms 628.0 KiB
#11 Accepted 31ms 532.0 KiB
#12 Accepted 999ms 83.719 MiB
#13 Accepted 118ms 624.0 KiB
#14 Accepted 642ms 60.539 MiB
#15 Accepted 515ms 53.902 MiB

Code

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <cstring>
#include <unordered_map>
#include <iomanip>
#include <queue>
#include <map>
#include <sstream>
#include <stack>
#include <bitset>
#include <random>

using ll = long long;

using namespace std;

constexpr int nm = 500002;

int n, m;
ll a[nm], c[nm], sum[nm];
int f[nm];

void add(vector<int> &tree, int i, int x) {
    while (i <= m) {
        tree[i] = max(tree[i], x);
        i += i & (-i);
    }
}

int query(vector<int> &tree, int i) {
    int res = -1e9;
    while (i > 0) {
        res = max(res, tree[i]);
        i -= i & (-i);
    }
    return res;
}

void solve() {
    cin >> n;
    vector<ll> vals{0};
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        vals.push_back(sum[i]);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        vals.push_back(sum[i] - c[i]);
    }

    if (n == 1) {
        cout << "0\n";
        return;
    }

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

    map<ll, int> id;
    m = 0;
    for (int i = 0; i < vals.size(); ++i) {
        if (i == 0 || vals[i] > vals[i - 1]) {
            id[vals[i]] = ++m;
        }
    }

    vector<int> tree(m + 1, -1e9);

    // sum[j] - sum[i - 1] >= c[j]
    // sum[i - 1] <= sum[j] - c[j]
    f[1] = 0;
    add(tree, id[0], 0);
    for (int i = 2; i <= n; ++i) {
        f[i] = query(tree, id[sum[i] - c[i]]) + 1;
        add(tree, id[sum[i - 1]], f[i]);
    }

    cout << (f[n] > 0 ? f[n] : -1) << "\n";
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);

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

Information

Submit By
Type
Submission
Problem
P1199 F. Roy and Path Game
Contest
Happy New Year 2026
Language
C++17 (G++ 13.2.0)
Submit At
2026-01-06 16:08:37
Judged At
2026-01-06 16:08:37
Judged By
Score
100
Total Time
999ms
Peak Memory
86.383 MiB