Submission #36005

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36005	2017-12-04T08:01:28 Z	Dat160601	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	499 ms	19312 KB

fortune_telling2

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 ^
fortune_telling2.cpp: In function 'int read()':
fortune_telling2.cpp:16: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	12960 KB	Output is correct
2	Correct	3 ms	12960 KB	Output is correct
3	Correct	0 ms	12960 KB	Output is correct
4	Correct	0 ms	12960 KB	Output is correct
5	Correct	0 ms	12960 KB	Output is correct
6	Correct	0 ms	12960 KB	Output is correct
7	Correct	3 ms	12960 KB	Output is correct
8	Correct	3 ms	12960 KB	Output is correct
9	Correct	3 ms	12960 KB	Output is correct
10	Correct	3 ms	12960 KB	Output is correct
11	Correct	0 ms	12960 KB	Output is correct
12	Correct	0 ms	12960 KB	Output is correct
13	Correct	3 ms	12960 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	13300 KB	Output is correct
2	Correct	29 ms	13560 KB	Output is correct
3	Correct	43 ms	13824 KB	Output is correct
4	Correct	73 ms	14212 KB	Output is correct
5	Correct	69 ms	14212 KB	Output is correct
6	Correct	73 ms	14212 KB	Output is correct
7	Correct	66 ms	14212 KB	Output is correct
8	Correct	66 ms	14080 KB	Output is correct
9	Correct	43 ms	14212 KB	Output is correct
10	Correct	39 ms	14212 KB	Output is correct
11	Correct	49 ms	14344 KB	Output is correct
12	Correct	43 ms	14080 KB	Output is correct
13	Correct	59 ms	14080 KB	Output is correct
14	Correct	63 ms	14080 KB	Output is correct
15	Correct	59 ms	14080 KB	Output is correct
16	Correct	49 ms	14212 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	16116 KB	Output is correct
2	Correct	179 ms	16276 KB	Output is correct
3	Correct	256 ms	17200 KB	Output is correct
4	Correct	459 ms	18652 KB	Output is correct
5	Correct	66 ms	16116 KB	Output is correct
6	Correct	499 ms	18652 KB	Output is correct
7	Correct	469 ms	18652 KB	Output is correct
8	Correct	436 ms	18652 KB	Output is correct
9	Correct	429 ms	18388 KB	Output is correct
10	Correct	476 ms	18784 KB	Output is correct
11	Correct	326 ms	17596 KB	Output is correct
12	Correct	453 ms	18652 KB	Output is correct
13	Correct	449 ms	18784 KB	Output is correct
14	Correct	179 ms	17664 KB	Output is correct
15	Correct	203 ms	17504 KB	Output is correct
16	Correct	236 ms	17284 KB	Output is correct
17	Correct	246 ms	18652 KB	Output is correct
18	Correct	233 ms	19312 KB	Output is correct
19	Correct	346 ms	18256 KB	Output is correct
20	Correct	346 ms	18256 KB	Output is correct