# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5;
int n,k,a[N],b[N],cnt, x[N],curj,aa,bb,mn,mx,frmt,frm,idd,ans;
vector <pii>v;
vector <pii> v1,v2;
int tree[4*N],tree1[N];
multiset <int> ms;
multiset <int> :: iterator it;
map <int, int > idx;
void upd(int idx, int val) {
for (int i = idx; i < N; i += i&(-i)) {
tree1[i] += val;
}
}
int get1(int idx) {
int pas = 0;
for (int i = idx; i > 0 ; i -= i&(-i)) {
pas += tree1[i];
}
return pas;
}
int get(int le, int ri) {
return get1(ri) - get1(le - 1);
}
void update(int node, int le, int ri, int idx, int val) {
if (le > idx || ri < idx) {
return ;
}
if (le == ri) {
tree[node] = max(tree[node],val);
return ;
}
int mid = (le + ri) / 2;
update(2*node, le, mid,idx,val);
update(2*node + 1, mid + 1, ri, idx, val);
tree[node] = max(tree[2*node],tree[2*node + 1]);
}
int getans(int node, int le, int ri, int start, int end) {
if (le > end || ri < start) return 0;
if (le >= start && ri <= end) {
return tree[node];
}
int mid = (le + ri) / 2;
return max(getans(2*node, le, mid, start,end), getans(2*node + 1, mid + 1, ri, start,end));
}
main() {
cin>>n>>k;
for (int i = 1; i <= n; i++) {
cin>>a[i]>>b[i];
v.pb({max(a[i],b[i]),i});
}
for (int i = 1; i <= k; i++) {
cin>>x[i];
v1.pb({x[i],i});
v2.pb({x[i],i});
ms.insert(x[i]);
}
ms.insert(1e9 + 1);
sort(v.begin(),v.end());reverse(v.begin(),v.end());
sort(v1.begin(),v1.end()); reverse(v1.begin(), v1.end());
v2.pb({1e9 + 1, 1});
sort(v2.begin(),v2.end());
idx[v2[0].f] = 1;
cnt = 1;
for (int i = 1; i < v2.size(); i++) {
if (v2[i].f != v2[i - 1].f) cnt++;
idx[v2[i].f] = cnt;
}
for (int i = 0; i < (int)v2.size() - 1; i++) {
// n??
update(1,1,n,idx[v2[i].f], v2[i].s);
// cout<<v2[i].f<<" "<<idx[v2[i].f]<<" "<<v2[i].s<<endl;
}
curj = 0;
for (int i = 0; i < v.size(); i++) {
// cout<<i<<" "<<v[i].f<<" "<<v[i].s<<endl;
while(curj < v1.size() && v1[curj].f >= v[i].f) {
//add(curj);
upd(v1[curj].s,1);
// cout<<v1[curj].s<<"s \n";
curj++;
}
aa = a[v[i].s]; bb = b[v[i].s]; mn = min(aa,bb); mx = max(aa,bb);
it = ms.lower_bound(mn); frmt = idx[*it];
// if (i == 2) cout<<"*it"<<*it<<endl;
it = ms.lower_bound(mx); frm = idx[(*it)] - 1;
// if (i == 2)
// cout<<frmt<<" "<<frm<<" "<<*it<<endl;
idd = 0;
if (frmt <= frm) {
idd = getans(1,1,n,frmt,frm);
if (idd != 0) aa = mx, bb = mn;
}
// cout<<idd<<" id\n";
//cout<<get(idd + 1, n)<<endl;
if (get(idd + 1, n) % 2 == 1) swap(aa,bb);
// cout<<aa<<"aaa"<<endl;
ans += aa;
}
cout<<ans<<"\n";
}
Compilation message
fortune_telling2.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
52 | main() {
| ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:71:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i = 1; i < v2.size(); i++) {
| ~~^~~~~~~~~~~
fortune_telling2.cpp:81:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
fortune_telling2.cpp:83:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | while(curj < v1.size() && v1[curj].f >= v[i].f) {
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
