QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#586834#8057. Best Carry Player 4XiaoTieWA 53ms3620kbC++173.1kb2024-09-24 15:53:182024-09-24 15:53:19

Judging History

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

  • [2024-09-24 15:53:19]
  • 评测
  • 测评结果:WA
  • 用时:53ms
  • 内存:3620kb
  • [2024-09-24 15:53:18]
  • 提交

answer

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <algorithm>
#include <stack>
#define int long long
#define endl "\n"
#define bit(x) (1LL << x)
#define inf (int)1e18
using namespace std;

typedef pair<int, int> PII;

template <typename T>
struct Fenwick
{
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0)
    {
        init(n_);
    }

    void init(int n_)
    {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v)
    {
        for (int i = x + 1; i <= n; i += i & -i)
        {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x)
    {
	    x ++;
        T ans{};
        for (int i = x; i > 0; i -= i & -i)
        {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r)
    {
        return sum(r) - sum(l - 1);
    }

    int select(const T &k)
    {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2)
        {
            if (x + i <= n && cur + a[x + i - 1] <= k)
            {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};     

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 7);
    vector<int> b(n + 7);
    int suma = 0, sumb = 0;
    for (int i = 0; i < n ; i ++)
        cin >> a[i], suma += a[i];
    for (int i = 0; i < n ; i ++)
        cin >> b[i], sumb += b[i];
    if (suma > sumb) 
        b[0] += suma - sumb;
    else 
        a[0] += sumb - suma;
    int l = 1, r = n - 1;
    int lst = n;
    int ans = 0;
    int l1 = n, r1 = n;
    while (l < n) {
        if (b[r] > 0)
            lst = r;
        if (a[l] > 0 && b[lst] > 0) {
            l1 = l, r1 = lst;
        }
        l ++, r --;
    }
    if (l1 == n && r1 == n) {
        cout << 0 << endl;
        return;
    }
    a[l1] --, b[r1] --;
    ans ++;
    // for (int i = 0; i < n ; i ++) {
    //     cerr << a[i] << " ";
    // }
    // cerr << endl;
    // for (int i = 0; i < n ; i ++) {
    //     cerr << b[i] << " ";
    // }
    // cerr << endl;
    l = n - 1, r = 0;
    stack<PII> stk;
    for (int i = n - 1 ; i >= 0 ; i --) {
        if (b[i] > 0)
            stk.push({b[i], i});
    }
    while (l >= 0) {
        while (stk.size() && stk.top().second < r)
            stk.pop();
        while (a[l] > 0 && stk.size()) {
            auto [t, id] = stk.top();
            stk.pop();
            if (a[l] < t) {
                ans += a[l];
                t -= a[l];
                a[l] = 0;
                stk.push({t, id});
            }
            else {
                ans += t;
                a[l] -= t;
                t = 0;
            }
        }
        l --, r ++;
    }
    cout << ans << endl;
}
// 2 1 3 4
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
// 0010001
// 0001111
// 0111110



// 2 1
// 3 0

// 10
// 5 3 5 3 2 4 2 4 1 5
// 0 3 9 8 9 8 9 8 9 8 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
2
1 2
3 4
3
1 0 1
0 1 0
4
1 0 0 1
1 1 1 1
5
123456 114514 1919810 233333 234567
20050815 998244353 0 0 0
10
5 3 5 3 2 4 2 4 1 5
9 9 8 2 4 4 3 5 3 0

output:

5
1
2
467900
29

result:

ok 5 number(s): "5 1 2 467900 29"

Test #2:

score: -100
Wrong Answer
time: 53ms
memory: 3596kb

input:

100000
5
0 1 1 1 1
0 0 1 0 0
5
0 0 0 0 0
1 1 1 0 0
5
0 0 2 1 1
0 2 1 0 1
5
0 0 0 0 0
1 2 1 0 0
5
0 1 0 1 1
0 0 1 1 1
5
2 0 0 0 1
1 0 0 0 3
5
2 0 0 1 1
0 2 1 1 1
5
0 0 0 0 2
0 0 0 0 1
5
0 0 0 0 0
0 1 1 0 0
5
4 0 0 0 0
0 0 0 1 0
5
0 0 0 0 1
2 1 1 0 0
5
0 2 3 0 0
0 0 0 1 0
5
1 1 1 0 1
1 0 1 0 1
5
0 0 0...

output:

1
0
4
0
3
3
3
2
0
0
1
1
2
0
3
0
0
0
0
0
0
0
3
0
4
1
0
2
3
2
1
4
0
0
2
0
0
1
1
0
0
3
4
3
1
2
2
0
1
2
2
2
0
3
0
2
1
1
0
1
0
4
0
0
2
2
0
3
3
0
2
0
1
0
0
1
1
2
0
2
4
0
2
5
0
1
1
0
0
0
2
1
3
0
2
0
4
3
3
0
2
1
0
1
3
1
1
0
0
0
1
0
3
2
2
0
2
1
1
0
1
0
0
2
4
1
2
2
1
2
2
0
1
0
0
2
3
1
3
1
0
2
2
3
0
1
1
0
1
1
...

result:

wrong answer 1st numbers differ - expected: '2', found: '1'