#include <bits/stdc++.h>
using namespace std;
/***********************************************/
/* Dear online judge:
* I've read the problem, and tried to solve it.
* Even if you don't accept my solution, you should respect my effort.
* I hope my code compiles and gets accepted.
* ___ __ _______ _______
* |\ \|\ \ |\ ___ \ |\ ___ \
* \ \ \/ /|_\ \ __/| \ \ __/|
* \ \ ___ \\ \ \_|/__\ \ \_|/__
* \ \ \\ \ \\ \ \_|\ \\ \ \_|\ \
* \ \__\\ \__\\ \_______\\ \_______\
* \|__| \|__| \|_______| \|_______|
*/
const long long mod = 1000000007;
const int mxN = 200010;
int mBIT[mxN];
int sBIT[mxN];
void upds(int ind,int val) {
while(ind >= 0) {
sBIT[ind] += val;
ind = (ind & (ind + 1)) - 1;
}
}
void updm(int ind,int val) {
while(ind >= 0) {
mBIT[ind] = max(mBIT[ind],val);
ind = (ind & (ind + 1)) - 1;
}
}
int gets(int ind) {
int res = 0;
while(ind < mxN) {
res += sBIT[ind];
ind |= ind + 1;
}
return res;
}
int getm(int ind) {
int res = 0;
while(ind < mxN) {
res = max(res,mBIT[ind]);
ind |= ind + 1;
}
return res;
}
bool cmp(pair<long long,long long> a,pair<long long,long long> b) {
return max(a.first,a.second) < max(b.first,b.second);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N,K;
cin>>N>>K;
vector<pair<long long,long long> > a(N);
for(int i = 0;i < N;i++) cin>>a[i].first;
for(int i = 0;i < N;i++) cin>>a[i].second;
sort(a.begin(),a.end(),cmp);
vector<pair<int,int> > o(K);
for(int i = 0;i < K;i++) cin>>o[i].first,upds(i,1),o[i].second = i;
sort(o.begin(),o.end());
long long res = 0;
for(int i = 0,j = 0;i < N;i++) {
while(j < K && o[j].first < max(a[i].first,a[i].second)) {
upds(o[j].second,-1);
updm(o[j].second,o[j].first);
j++;
}
int lo = 0,hi = K-1,out = 0;
while(lo <= hi) {
int md = (lo + hi)>>1;
if(getm(md) >= min(a[i].first,a[i].second)) out = md + 1,lo = md + 1;
else hi = md - 1;
}
{
out = 0;
for(int m = 0;m < K;m++) {
if(o[m].first < max(a[i].first,a[i].second) && o[m].first >= min(a[i].first,a[i].second))
out = max(out,o[m].second+1);
}
}
int get = gets(out);
{
get = 0;
for(int m = 0;m < K;m++) {
if(o[m].first >= max(a[i].first,a[i].second) && o[m].second >= out)
get++;
}
}
if(out == 0) {
assert(get == K - j);
res += (get&1?a[i].second:a[i].first);
} else {
assert(get <= K - j);
if(a[i].second > a[i].first) {
res += (get&1?a[i].first:a[i].second);
} else {
res += (get&1?a[i].second:a[i].first);
}
}
}
cout<<res;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
211 ms |
876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2061 ms |
3744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
