#include<bits/stdc++.h> using namespace std; const int MAXN = 202020; namespace wavelet { vector<int> wavelet[2*MAXN]; vector<int> leftind[2*MAXN]; vector<int> orig[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) { //printf("=%d %d %d %d\n", from, to, K, ind); if(from > to) return 0; if(maxv[ind] < K) return 0; if(minv[ind] >= K) return to-from+1; int ls, rs, le, re; if(wavelet[ind][from] <= (maxv[ind]+minv[ind])/2) { ls = leftind[ind][from]-1; rs = from-ls; } else { ls = leftind[ind][from]; rs = from-ls; } if(wavelet[ind][to] <= (maxv[ind]+minv[ind])/2) { le = leftind[ind][to]-1; re = to-1-le; } else { le = leftind[ind][to]-1; re = to-1-le; } return count_ge(ls, le, K, lchild[ind]) + count_ge(rs, re, K, rchild[ind]); } int find_inside(int from, int to, int ind) { if(from > to) return -1; if(to < minv[ind]) return -1; if(maxv[ind] < from) return -1; if(from <= minv[ind] && maxv[ind] <= to) return orig[ind].back(); return max(find_inside(from, to, lchild[ind]), find_inside(from, to, 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); //printf("%d %d %d [%d, %d]\n", mi, cntl, cntr, from, to); 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]); orig[lchild[ind]].push_back(orig[ind][i]); } else { wavelet[rchild[ind]].push_back(wavelet[ind][i]); orig[rchild[ind]].push_back(orig[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::orig[wavelet::gind].push_back(i); } 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 = max(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("%d %d %d\n", ind, cnt, now); } printf("%lld\n", ans); }

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:127: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:129: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:133:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t; scanf("%d", &t);
                ~~~~~^~~~~~~~~~