#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) (v).begin(),(v).end()
const int N = 200005, sz = 262144;
int n, m, a[N], b[N], c[N], t[N], x[N];
ll r;
struct Seg{
vector<int> v[2 * sz];
int u(int x, int y){
for(x += sz; x; x >>= 1) v[x].push_back(y);
}
int m(int s, int e){
int r = 0;
for(s += sz, e += sz; s <= e; s >>= 1, e >>= 1){
if( s & 1){ if(!v[s].empty()) r = max(r, v[s].back()); s++; }
if(~e & 1){ if(!v[e].empty()) r = max(r, v[e].back()); e--; }
}
return r;
}
int c(int s, int e, int x){
int r = 0;
for(s += sz, e += sz; s <= e; s >>= 1, e >>= 1){
if( s & 1){ r ^= int(v[s].end() - lower_bound(all(v[s]), x)); s++; }
if(~e & 1){ r ^= int(v[e].end() - lower_bound(all(v[e]), x)); e--; }
}
return r & 1;
}
} S;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d%d", a + i, b + i);
if(a[i] > b[i]){ c[i] = 1; swap(a[i], b[i]); }
}
for(int i = 1; i <= m; i++){
scanf("%d", t + i);
x[i - 1] = t[i];
}
sort(x, x + m);
for(int i = 1; i <= m; i++){
t[i] = int(lower_bound(x, x + n, t[i]) - x + 1);
S.u(t[i], i);
}
for(int i = 1; i <= n; i++){
int p = int(lower_bound(x, x + n, a[i]) - x + 1);
int q = int(lower_bound(x, x + n, b[i]) - x);
int t = S.m(p, q);
r += (S.c(q + 1, m, t + 1) ^ (!t & !c[i])) ? a[i] : b[i];
}
printf("%lld\n", r);
}
Compilation message
fortune_telling2.cpp: In member function 'int Seg::u(int, int)':
fortune_telling2.cpp:15:5: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:37: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:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", t + i);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
12792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
12792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
12792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
