#include <cstdio>
#include <cstring>
#define NDEBUG
#include <cassert>
#include <algorithm>
#include <vector>
#include <functional>
using ll = long long;
const int MN = 2e5+10, MK = 2e5+10, MV = MN*2+MK, MX = 1.5e7;//MX = 1.5e7
int s[MX], c[MX][2], X=1, v[MV], V, a[MN], b[MN], t[MK], N, K, n[MV], r[MN];
struct evt{public:int v, id;bool operator < (evt o)const{return v>o.v;}};//reversed sort
std::vector<evt> q;
ll f;
int upd(int n, int l, int r, int q, int v)
{
assert(++X<MX);
if(n)
{
memcpy(c[X], c[n], 8);
s[X]=s[n];
}
n=X;
s[n]+=v;
if(r-l>1)
{
int m=l+(r-l)/2;
if(q<m) c[n][0]=upd(c[n][0], l, m, q, v);
else c[n][1]=upd(c[n][1], m, r, q, v);
assert(s[n] == s[c[n][0]] + s[c[n][1]]);
}
return n;
}
int diff(int n, int m, int l, int r)
{
if(r-l>1)
{
int m=l+(r-l)/2;
if(s[c[n][1]] != s[c[m][1]]) return diff(c[n][1], c[m][1], m, r);
else return diff(c[n][0], c[m][0], l, m);
}
else
return l;
}
int qry(int n, int l, int r, int ql, int qr)
{
if(!n) return 0;
if(ql <= l&&r <= qr) return s[n];
else
{
int m=l+(r-l)/2, f=0;
if(ql<m) f+=qry(c[n][0], l, m, ql, qr);
if(m<qr) f+=qry(c[n][1], m, r, ql, qr);
return f;
}
}
int main()
{
scanf("%d%d", &N, &K);
for(int i=0;i<N;++i)
{
scanf("%d", a+i), v[V++]=a[i];
scanf("%d", b+i), v[V++]=b[i];
}
for(int i=0;i<K;++i) scanf("%d", t+i), v[V++]=t[i];
std::sort(v, v+V);
V = std::unique(v, v+V)-v;
//for(int i=0;i<V;++i) printf("%d%c", v[i], " \n"[i+1==V]);
for(int i=0;i<K;++i)
t[i]=std::lower_bound(v, v+V, t[i])-v, q.push_back({t[i], i});
std::sort(q.begin(), q.end());
r[V]=1;
for(int i=V-1,j=0;i>=0;--i)
{
r[i]=r[i+1];
for(;j<q.size()&&q[j].v==i;++j)//greater or equ
r[i] = upd(r[i], 0, K, q[j].id, 1);
//printf("NUM: %d: %d\n", v[i], s[r[i]]);
}
for(int i=0;i<N;++i)
{
a[i]=std::lower_bound(v, v+V, a[i])-v;
b[i]=std::lower_bound(v, v+V, b[i])-v;
//printf("TESTALL(%d,%d): %d %d\n", v[a[i]], v[b[i]], s[r[a[i]]], s[r[b[i]]]);
if(s[r[a[i]]] == s[r[b[i]]])
if(s[r[a[i]]]&1)
f+=v[b[i]];
else
f+=v[a[i]];
else
{
assert(a[i]!=b[i]);
int t=diff(r[a[i]], r[b[i]], 0, K), u=t+1<K?qry(r[a[i]], 0, K, t+1, K):0;//for finding u, result should be same for r[a[i]] and r[b[i]]
//greater one is selected, then perform u queries
//printf("%d: %d %d\n", i, t, u);
if(b[i]>a[i])++u;
if(u&1)
f+=v[b[i]];
else
f+=v[a[i]];
}
}
printf("%lld\n", f);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:78:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;j<q.size()&&q[j].v==i;++j)//greater or equ
~^~~~~~~~~
fortune_telling2.cpp:61:7: 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:64:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a+i), v[V++]=a[i];
~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:65:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", b+i), v[V++]=b[i];
~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:67:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0;i<K;++i) scanf("%d", t+i), v[V++]=t[i];
~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
