oj.uz

Submission #36004

# Submission time Handle Problem Language Result Execution time Memory
36004 2017-12-04T07:56:36 Z Dat160601 Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 479 ms 19308 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<=q;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(q)-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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12956 KB Output is correct
2 Correct 0 ms 12956 KB Output is correct
3 Correct 0 ms 12956 KB Output is correct
4 Correct 3 ms 12956 KB Output is correct
5 Correct 3 ms 12956 KB Output is correct
6 Correct 0 ms 12956 KB Output is correct
7 Correct 0 ms 12956 KB Output is correct
8 Correct 0 ms 12956 KB Output is correct
9 Correct 3 ms 12956 KB Output is correct
10 Correct 3 ms 12956 KB Output is correct
11 Correct 6 ms 12956 KB Output is correct
12 Correct 6 ms 12956 KB Output is correct
13 Correct 0 ms 12956 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13296 KB Output is correct
2 Correct 23 ms 13556 KB Output is correct
3 Correct 49 ms 13820 KB Output is correct
4 Correct 76 ms 14208 KB Output is correct
5 Correct 73 ms 14208 KB Output is correct
6 Correct 63 ms 14208 KB Output is correct
7 Correct 69 ms 14208 KB Output is correct
8 Correct 59 ms 14076 KB Output is correct
9 Correct 49 ms 14208 KB Output is correct
10 Correct 49 ms 14208 KB Output is correct
11 Correct 53 ms 14340 KB Output is correct
12 Correct 43 ms 14076 KB Output is correct
13 Correct 56 ms 14076 KB Output is correct
14 Correct 59 ms 14076 KB Output is correct
15 Correct 63 ms 14076 KB Output is correct
16 Correct 59 ms 14208 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 16112 KB Output is correct
2 Correct 153 ms 16272 KB Output is correct
3 Correct 306 ms 17196 KB Output is correct
4 Correct 443 ms 18648 KB Output is correct
5 Correct 66 ms 16112 KB Output is correct
6 Correct 436 ms 18648 KB Output is correct
7 Correct 469 ms 18648 KB Output is correct
8 Correct 453 ms 18648 KB Output is correct
9 Correct 473 ms 18384 KB Output is correct
10 Correct 463 ms 18780 KB Output is correct
11 Correct 379 ms 17592 KB Output is correct
12 Correct 479 ms 18648 KB Output is correct
13 Correct 473 ms 18780 KB Output is correct
14 Correct 209 ms 17660 KB Output is correct
15 Correct 243 ms 17500 KB Output is correct
16 Correct 253 ms 17280 KB Output is correct
17 Correct 246 ms 18648 KB Output is correct
18 Correct 229 ms 19308 KB Output is correct
19 Correct 409 ms 18252 KB Output is correct
20 Correct 376 ms 18252 KB Output is correct