#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define mid (start+end)/2
const int N = 2e5+2;
const int M=N*12,N2=N*3;
int A[N],B[N],arr[N],T[N];
int ans[N*2];
int TREE2[M];
int D[N],X[N],Y[N];
int bit[N2];
int act[N2];
int G;
void update2(int idx, int start, int end, int x, int v) {
if(start==end) TREE2[idx]=v;
else if(x<=mid) update2(idx*2, start, mid, x, v);
else update2(idx*2+1, mid+1, end, x, v);
TREE2[idx]=v;
}
int query2(int idx, int start, int end, int a, int b) {
if(b<a) return 0;
if(start>=a && end<=b) return TREE2[idx];
else if(start>b || end<a) return 0;
else return max(query2(idx*2, start, mid,a,b),query2(idx*2+1, mid+1, end,a,b));
}
void add(int i, int v) {
while (i<=N2) {
bit[i]+=v;
i+=(i&-i);
}
}
int smquery(int i) {
int sum=0;
while (i>0) {
sum+=bit[i];
i-=(i&-i);
}
return sum;
}
int main() {
vector<pair<int, pair<int, int>>> vt;
int n,k,x;scanf("%d %d",&n,&k);
for (int i=1; i<=n; i++) {
scanf("%d",&x);
vt.push_back({x,{1,i}});
scanf("%d",&x);
vt.push_back({x,{2,i}});
}
for (int i=1; i<=k; i++) {
scanf("%d",&x);
vt.push_back({x,{3,i}});
}
sort(vt.begin(),vt.end());
int i=0,h,g=0;
while (i<vt.size()) {
h=vt[i].first;
g++;
act[g]=h;
while (i<vt.size() && vt[i].first==h) {
x=vt[i].second.second;
if(vt[i].second.first==1) {
A[x]=g;
}
else if(vt[i].second.first==2) {
B[x]=g;
}
else {
T[x]=g;
}
i++;
}
}
G=g;
for (int i=1; i<=k; i++) {
update2(1, 1, g, T[i], i);
}
vt.clear();
int y,c,z;
int f=0;
for (int i=1; i<=n; i++) {
x=min(A[i],B[i]);
y=max(A[i],B[i]);
c=query2(1, 1, g, x, y-1);
if(c==0) {
D[i]=0;
f++;
X[i]=f;
vt.push_back({k,{y,f}});
}
else {
D[i]=1;
f++;
X[i]=f;
vt.push_back({k,{y,f}});
f++;
Y[i]=f;
vt.push_back({c,{y,f}});
}
}
int j=1;
sort(vt.begin(),vt.end());
for(auto qr:vt) {
x=qr.first;
y=qr.second.first;
z=qr.second.second;
while (j<=x) {
add(T[j], 1);
j++;
}
ans[z]=smquery(g)-smquery(y-1);
}
int total=0;
for (int i=1; i<=n; i++) {
x=min(A[i],B[i]);
y=max(A[i],B[i]);
if(D[i]==0) {
if(ans[X[i]]%2==0) total+=act[A[i]];
else total+=act[B[i]];
}
else {
c=ans[X[i]]-ans[Y[i]];
if(c%2==0) total+=act[y];
else total+=act[x];
}
}
cout<<total<<endl;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i<vt.size()) {
^
fortune_telling2.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i<vt.size() && vt[i].first==h) {
^
fortune_telling2.cpp:51:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n,k,x;scanf("%d %d",&n,&k);
^
fortune_telling2.cpp:53:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
fortune_telling2.cpp:55:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
fortune_telling2.cpp:59:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
23116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
27808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
