QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#786016#4963. Numbers on both SidesLaVuna47#WA 0ms3832kbC++203.5kb2024-11-26 19:56:022024-11-26 19:56:05

Judging History

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

  • [2024-11-26 19:56:05]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2024-11-26 19:56:02]
  • 提交

answer

/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif


// segment tree with sum binary operation
struct SegTree
{
    vector<ll> T;
    int n;

    // Root of the tree has index 1.
    // Zero based indexing of A.
    SegTree(const vector<ll>& A)
    {
        n = sz(A);
        T = vector<ll>(2*n, 0);
        for (int i = 0; i < n; ++i)
            T[i+n] = A[i];
        build();
    }

    SegTree(int nn)
    {
        this->n = nn;
        T = vector<ll>(2*n, 0);
    }

    // [l; r)
    ll query(int l, int r)
    {
        ll res = 0;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1)
        {
            if(l & 1) res += T[l++];
            if(r & 1) res += T[--r];
        }
        return res;
    }

    void add(int p, ll delta)
    {
        for (T[p += n] += delta; p > 1; p >>= 1)
            T[p >> 1] = T[p] + T[p ^ 1];
    }

    void build()
    {
        for (int i = n-1; i >= 1; --i)
            T[i] = T[i << 1] + T[i << 1 ^ 1];
    }
};

int solve()
{
	int n;
	if(!(cin >> n))
		return 1;
	vector<ll> a(n);
	vector<ll> b(n);
	FOR(i,0,n) cin >> a[i];
	FOR(i,0,n) cin >> b[i];
	vector<int> II(n+47);
	{
		unordered_map<ll, ll> I;
		set<ll> S;
		for(auto item: b)
			S.insert(item);
		int ctr = 1;
		for(auto item: S)
			I[item] = ctr++;
		for(auto& item: b)
		{
			ll orig = item;
			item = I[item]; 
			II[item] = orig;
		}
	}
	ll K, L;
	cin >> K >> L;
	
	ll as = 0;
	SegTree segC(n+47), segS(n+47);
	FOR(i,0,K) as += a[i], segC.add(b[i], 1), segS.add(b[i], II[i]);
	
	auto query = [&]() -> ll {
		int R = n+44;
		int l = 0, r = n+44;
		while(r-l>1)
		{
			int mid = (l+r)/2;
			if(segC.query(mid,R) < L)
				r = mid;
			else
				l = mid;
		}
		if(segC.query(r,R) < L)
			l = r;
		int t = l;
		--t;
		assert(segC.query(t,R) >= L);
		assert(segC.query(t+1,R) < L);
		int left = L-segC.query(t+1, R);
		ll res = segS.query(t+1,R);
		res += II[t]*left;
		return res;
	};

	ll res = as+query();
	for(int i = K-1, j = n-1; i >= 0; --i, --j)
	{
		as -= a[i];
		as += a[j];
		segC.add(b[i], -1);
		segS.add(b[i], -II[i]);
		segC.add(b[j], 1);
		segS.add(b[j], II[j]);
		res = max(res, as+query());
	}
	cout << res << '\n';
    return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1e9;
    //cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        if (solve())
        {
            break;
        }
#ifdef ONPC
        cout << "__________________________" << endl;
#endif
    }
#ifdef ONPC
    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

详细

Test #1:

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

input:

5
9 7 2 2 9
5 2 2 3 1
2 1

output:

23

result:

ok single line: '23'

Test #2:

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

input:

5
9 7 2 2 9
5 9 2 3 1
2 1

output:

25

result:

ok single line: '25'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3552kb

input:

10
53580627 697780592 429665569 16172712 200486124 435516652 711503384 868083709 616939240 492192996
746044490 57589903 507886672 433841177 918380467 426664522 281530079 729659740 980794901 914640542
8 6

output:

7592522869

result:

wrong answer 1st lines differ - expected: '8792267986', found: '7592522869'