oj.uz

답안 #36005

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36005 2017-12-04T08:01:28 Z Dat160601 운세 보기 2 (JOI14_fortune_telling2) C++14
100 / 100
 499 ms 19312 KB 
#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

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

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

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