#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 200'032;
const int S0 = 32767;
const int S1 = 2048;
int a[N], b[N];
short sa[N], sb[N];
int q[N];
short sq[N];
int n;
__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void up(short x, short y, short z, int l, int r)
{
Loop (i,l,r) {
short v = sa[i], u = sb[i];
v ^= v <= x? u: 0;
v ^= v <= y? u: 0;
v ^= v <= z? u: 0;
sa[i] = v;
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int k;
cin >> n >> k;
Loop (i,0,n)
cin >> a[i] >> b[i];
Loop (i,0,k)
cin >> q[i];
ll ans = 0;
for (int l0 = 0; l0 < n; l0 += S0) {
int r0 = min(n, l0+S0);
vector<int> vec = {0};
Loop (i,l0,r0) {
vec.push_back(a[i]);
vec.push_back(b[i]);
}
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
Loop (i,l0,r0) {
sa[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
sb[i] = lower_bound(vec.begin(), vec.end(), b[i]) - vec.begin();
sb[i] ^= sa[i];
}
Loop (i,0,k)
sq[i] = upper_bound(vec.begin(), vec.end(), q[i]) - vec.begin() - 1;
for (int l1 = l0; l1 < r0; l1 += S1) {
int r1 = min(r0, l1+S1);
for (int i = 0; i < k; i += 3)
up(sq[i+0], sq[i+1], sq[i+2], l1, r1);
}
Loop (i,l0,r0)
ans += vec[sa[i]];
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
15 ms |
688 KB |
Output is correct |
| 15 |
Runtime error |
41 ms |
1768 KB |
Execution killed with signal 11 |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
15 ms |
688 KB |
Output is correct |
| 15 |
Runtime error |
41 ms |
1768 KB |
Execution killed with signal 11 |
| 16 |
Halted |
0 ms |
0 KB |
- |
