#include<bits/stdc++.h>
using namespace std;
const int MAXN = 202020;
namespace wavelet
{
vector<int> wavelet[2*MAXN];
vector<int> leftind[2*MAXN];
int minv[2*MAXN];
int maxv[2*MAXN];
int lchild[2*MAXN];
int rchild[2*MAXN];
int gind = 0;
inline int lchildind(int ind, int x)
{
return leftind[ind][x]-1;
}
inline int rchildind(int ind, int x)
{
return x-leftind[ind][x];
}
int count_ge(int from, int to, int K, int ind)
{
if(from > to) return 0;
if(maxv[ind] < K) return 0;
if(minv[ind] >= K) return from-to+1;
return count_ge(lchildind(ind, from), lchildind(ind, to), K, lchild[ind])
+ count_ge(rchildind(ind, from), rchildind(ind, to), K, rchild[ind]);
}
int find_inside(int from, int to)
{
int N = wavelet[0].size();
int lo = -1; //here must be answer
int hi = N; //here mustn't be answer;
while(lo+1!=hi)
{
int mi = (lo+hi)/2;
int cntl = count_ge(mi, N-1, to+1, 0);
int cntr = count_ge(mi, N-1, from, 0);
if(cntl == cntr) lo = mi;
else hi = mi;
}
return lo;
}
void build_wavelet(int ind)
{
int N = wavelet[ind].size();
minv[ind] = *min_element(wavelet[ind].begin(), wavelet[ind].end());
maxv[ind] = *max_element(wavelet[ind].begin(), wavelet[ind].end());
if(minv[ind] == maxv[ind]) return;
lchild[ind] = gind++;
rchild[ind] = gind++;
int midv = (minv[ind]+maxv[ind])/2;
//minv[ind] ~ midv, midv+1, maxv[ind]
int p = 0;
for(int i=0; i<N; ++i)
{
if(wavelet[ind][i] <= midv)
{
++p;
wavelet[lchild[ind]].push_back(wavelet[ind][i]);
}
else
wavelet[rchild[ind]].push_back(wavelet[ind][i]);
leftind[ind].push_back(p);
}
build_wavelet(lchild[ind]);
build_wavelet(rchild[ind]);
}
};
int N, K;
int A[MAXN];
int B[MAXN];
int T[MAXN];
int main()
{
scanf("%d%d", &N, &K);
for(int i=0; i<N; ++i)
scanf("%d%d", A+i, B+i);
for(int i=0; i<K; ++i)
{
int t; scanf("%d", &t);
wavelet::wavelet[wavelet::gind].push_back(t);
}
wavelet::build_wavelet(wavelet::gind++);
long long ans = 0;
for(int i=0; i<N; ++i)
{
int small = min(A[i], B[i]);
int large = min(A[i], B[i]);
int ind = wavelet::find_inside(small, large-1);
int now = A[i];
if(ind != -1) now = large;
int cnt = wavelet::count_ge(ind+1, K-1, large, 0);
if(cnt&1) now = small+large-now;
ans += now;
}
printf("%lld\n", ans);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &K);
~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", A+i, B+i);
~~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:91:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int t; scanf("%d", &t);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
19576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
19576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
19576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
