oj.uz

Submission #36002

# Submission time Handle Problem Language Result Execution time Memory
36002 2017-12-04T07:42:44 Z Dat160601 Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 96 ms 16112 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int n,q;
int a[200007],b[200007],bit[200007],it[800007],res[200007];
long long ans=0;
vector < pair <int,int> > query,qr[200007];
int read(){
	int x;
	scanf("%d",&x);
	return x;
}
void upd(int pos){
	for(int i=pos;i<=n;i+=i&-i){
		bit[i]++;
	}
}
long long get(int pos){
	long long res=0;
	for(int i=pos;i>=1;i-=i&-i){
		res+=bit[i];
	}
	return res;
}
void init(int k,int l,int r){
	if(l==r){
		it[k]=query[l-1].se;
		return;
	}
	int mid=(l+r)/2;
	init(k*2,l,mid);
	init(k*2+1,mid+1,r);
	it[k]=max(it[k*2],it[k*2+1]);
}
int get(int k,int l,int r,int L,int R){
	if(l>R || r<L || l>r) return 0;
	if(l>=L && r<=R){
		return it[k];
	}
	int mid=(l+r)/2;
	return max(get(k*2,l,mid,L,R),get(k*2+1,mid+1,r,L,R));
}
int main(){
	n=read();
	q=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		b[i]=read();
	}
	for(int i=1;i<=q;i++){
		int val=read();
		query.pb(mp(val,i));
	}
	sort(query.begin(),query.end());
	init(1,1,q);
	for(int i=1;i<=n;i++){
		int mi=min(a[i],b[i]);
		int mx=max(a[i],b[i]);
		int lef=lower_bound(query.begin(),query.end(),mp(mi,0))-query.begin();
		int rig=lower_bound(query.begin(),query.end(),mp(mx,0))-query.begin()-1;
		lef++;
		rig++;
		//cout<<lef<<" "<<rig<<" "<<get(1,1,q,lef,rig)<<endl;
		if(lef<=rig){
			qr[rig+1].pb(mp(i,get(1,1,q,lef,rig)));
			if(a[i]<b[i]) swap(a[i],b[i]);
		}
		else{
			qr[rig+1].pb(mp(i,1));
		}
	}
	for(int i=q;i>=1;i--){
		upd(query[i-1].se);
		for(int j=0;j<(int)qr[i].size();j++){
			int x=qr[i][j].fi;
			res[x]=(get(n)-get(qr[i][j].se-1))%2;
		}
	}
	for(int i=1;i<=n;i++){
		if(res[i]==0) ans+=a[i];
		else ans+=b[i];
	}
	printf("%lld",ans);
}

Compilation message

fortune_telling2.cpp: In function 'int read()':
fortune_telling2.cpp:13:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&x);
                ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 12956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 13296 KB Output is correct
2 Correct 33 ms 13556 KB Output is correct
3 Correct 46 ms 13820 KB Output is correct
4 Correct 73 ms 14208 KB Output is correct
5 Correct 69 ms 14208 KB Output is correct
6 Correct 63 ms 14208 KB Output is correct
7 Correct 73 ms 14208 KB Output is correct
8 Correct 56 ms 14076 KB Output is correct
9 Correct 46 ms 14208 KB Output is correct
10 Correct 39 ms 14208 KB Output is correct
11 Correct 39 ms 14340 KB Output is correct
12 Correct 39 ms 14076 KB Output is correct
13 Incorrect 43 ms 14076 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 16112 KB Output isn't correct
2 Halted 0 ms 0 KB -