QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786016 | #4963. Numbers on both Sides | LaVuna47# | WA | 0ms | 3832kb | C++20 | 3.5kb | 2024-11-26 19:56:02 | 2024-11-26 19:56:05 |
Judging History
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
}
Details
Tip: Click on the bar to expand more detailed information
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'