#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
int mySum(int a, int b) {return a+b;}
int myMax(int a, int b) {return max(a, b);}
struct IDX {
int P; vector<int> val;
int initV;
function<int(int, int)> f;
IDX(int n, function<int(int, int)> ff) {
for(P=1; P<n; P<<=1);
val = vector<int>(2*P);
f = ff;
}
void init(int v) {
initV = v;
val = vector<int>(2*P, v);
}
void update(int v, int k) {
v += P;
val[v] = f(val[v], k);
while(v/=2) val[v] = f(val[v*2], val[v*2+1]);
}
int getF(int a, int b) {
a += P; b += P;
int res = initV;
while(a<=b) {
if(a%2==1) res = f(res, val[a++]);
if(b%2==0) res = f(res, val[b--]);
a>>=1;b>>=1;
}
return res;
}
};
struct IDXNR {
int P; vector<vector<int>> val;
IDXNR(int n, int q[]) {
for(P=1; P<n; P<<=1);
val = vector<vector<int>>(2*P);
for(int i=0; i<n; i++) val[P+i].push_back(q[i]);
for(int i=P-1; i>=1; i--) {
for(int x : val[i*2]) val[i].push_back(x);
for(int x : val[i*2+1]) val[i].push_back(x);
sort(ALL(val[i]));
}
}
int getK(int a, int b, int k) {
a += P; b += P;
int res = 0;
while(a<=b) {
if(a%2==1) res += val[a].end() - lower_bound(ALL(val[a]), k), a++;
if(b%2==0) res += val[b].end() - lower_bound(ALL(val[b]), k), b--;
a>>=1;b>>=1;
}
return res;
}
};
const int MAX_N = 2e5 + 100;
int N, Nr[MAX_N][2], Q[MAX_N], K;
vector<int> Co;
int main() {
cin >> N >> K;
REP(i, N) REP(j, 2) scanf("%d", &Nr[i][j]), Co.push_back(Nr[i][j]);
REP(i, K) scanf("%d", &Q[i]), Co.push_back(Q[i]);
sort(ALL(Co)); Co.erase(unique(ALL(Co)), Co.end());
REP(i, N) REP(j, 2) Nr[i][j] = lower_bound(ALL(Co), Nr[i][j]) - Co.begin();
REP(i, K) Q[i] = lower_bound(ALL(Co), Q[i]) - Co.begin();
IDX idxM = IDX(SZ(Co), myMax); idxM.init(-INF);
REP(i, K) idxM.update(Q[i], i);
IDXNR idxnr = IDXNR(K, Q);
ll ans = 0;
REP(i, N) {
int minV = min(Nr[i][0], Nr[i][1]), maxV = max(Nr[i][0], Nr[i][1]);
int ix = idxM.getF(minV, maxV-1);
if(ix < 0) ix = 0;
int cnt = idxnr.getK(ix, K-1, maxV);
if(cnt % 2) swap(Nr[i][0], Nr[i][1]);
// printf("ix %d | cnt %d | %d %d\n", ix, cnt, Nr[i][0], Nr[i][1]);
ans += Co[Nr[i][0]];
}
printf("%lld\n", ans);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:77:68: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
REP(i, N) REP(j, 2) scanf("%d", &Nr[i][j]), Co.push_back(Nr[i][j]);
^
fortune_telling2.cpp:78:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
REP(i, K) scanf("%d", &Q[i]), Co.push_back(Q[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
4548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
336 ms |
45636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
