//by yjz
#include<bits/stdc++.h>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
typedef long long ll;
using namespace std;
const int maxn = 400111;
const int inf = 1e9;
int n, m, arr[maxn];
#define ls p<<1
#define rs p<<1|1
int mn[maxn<<4], cnt[maxn<<4];
void update(int p)
{
mn[p] = min(mn[ls], mn[rs]);
cnt[p] = cnt[ls]+cnt[rs];
}
void modify(int x, int v, int l, int r, int p)
{
if (l==r)
{
mn[p] = v;
cnt[p] = v<inf;
return;
}
int m = l+r>>1;
if (x<=m) modify(x, v, l, m, ls);
else modify(x, v, m+1, r, rs);
update(p);
}
int query_last(int v, int l, int r, int p)
{
if (mn[p]>=v) return l-1;
if (l==r) return l;
int m = l+r>>1;
int tmp = query_last(v, m+1, r, rs);
if (tmp==m) return query_last(v, l, m, ls);
else return tmp;
}
int query_cnt(int x, int y, int l, int r, int p)
{
if (y<l||r<x) return 0;
if (x<=l&&r<=y) return cnt[p];
int m = l+r>>1;
return query_cnt(x, y, l, m, ls)+query_cnt(x, y, m+1, r, rs);
}
vector<int> pts;
int getid(int x) {return lower_bound(pts.begin(), pts.end(), x+1)-pts.begin();}
pair<int,int> p[maxn];
vector<int> v_arr[maxn], v_p[maxn], v_qr[maxn];
int lst[maxn];
bool f[maxn];
int main()
{
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++)
{
scanf("%d%d", &p[i].FF, &p[i].SS);
pts.PB(p[i].FF);
pts.PB(p[i].SS);
}
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());
int sz = pts.size();
for (int i=1; i<=n; i++)
{
p[i].FF = getid(p[i].FF), p[i].SS = getid(p[i].SS);
if (p[i].FF>p[i].SS) swap(p[i].FF, p[i].SS), f[i] = true;
v_p[p[i].FF].PB(i);
v_qr[p[i].SS].PB(i);
}
for (int i=1; i<=m; i++)
{
scanf("%d", &arr[i]);
arr[i] = getid(arr[i]);
v_arr[arr[i]].PB(i);
modify(i, arr[i], 1, m, 1);
}
// for (int i=1; i<=n; i++) cerr<<p[i].FF<<","<<p[i].SS<<endl;
// for (int i=1; i<=m; i++) cerr<<arr[i]<<" "; cerr<<endl;
for (int i=1; i<=sz; i++)
{
for (auto t : v_p[i])
{
lst[t] = query_last(p[t].SS, 1, m, 1);
if (lst[t]!=0) f[t] = true;
}
for (auto t : v_qr[i])
{
f[t] ^= query_cnt(lst[t]+1, m, 1, m, 1)&1;
}
for (auto t : v_arr[i])
{
modify(t, inf, 1, m, 1);
}
}
ll ans = 0;
for (int i=1; i<=n; i++)
{
int x = p[i].FF, y = p[i].SS;
bool flip = f[i];
if (flip) ans += pts[y-1]; else ans += pts[x-1];
}
cout<<ans<<endl;
return 0;
}
/*
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
*/
Compilation message
fortune_telling2.cpp: In function 'void modify(int, int, int, int, int)':
fortune_telling2.cpp:28:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l+r>>1;
~^~
fortune_telling2.cpp: In function 'int query_last(int, int, int, int)':
fortune_telling2.cpp:37:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l+r>>1;
~^~
fortune_telling2.cpp: In function 'int query_cnt(int, int, int, int, int)':
fortune_telling2.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l+r>>1;
~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:57:7: 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:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &p[i].FF, &p[i].SS);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &arr[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
28664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
28664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
28664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
