oj.uz

답안 #36002

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36002 2017-12-04T07:42:44 Z Dat160601 운세 보기 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 12956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 16112 KB Output isn't correct
2 Halted 0 ms 0 KB -