Submission #110757

#	Time	Username	Problem	Language	Result	Execution time	Memory
110757		autumn_eel	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	493 ms	31400 KiB

fortune_telling2

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<int,int>P;
typedef long long ll;

struct Segtree{
	int N;
	vector<int>dat;
	Segtree(int n){
		N=1;while(N<n)N<<=1;
		dat=vector<int>(2*N,-1);
	}
	void update(int k,int x){
		k+=N;
		dat[k]=x;
		while(k>1){
			k/=2;
			dat[k]=max(dat[k*2],dat[k*2+1]);
		}
	}
	int query(int l,int r){
		int res=-1;
		for(l+=N,r+=N;l<r;l>>=1,r>>=1){
			if(l&1)res=max(res,dat[l++]);
			if(r&1)res=max(res,dat[--r]);
		}
		return res;
	}
};

struct BIT{
	vector<int>bit;
	BIT(int n){
		bit=vector<int>(n+10);
	}
	void add(int k,int x){
		k++;
		while(k<bit.size()){
			bit[k]+=x;
			k+=k&-k;
		}
	}
	int sum(int k){
		k++;
		int res=0;
		while(k){
			res+=bit[k];
			k-=k&-k;
		}
		return res;
	}
};

int a[300000],b[300000];
int t[300000];
vector<P>query[300000];
int ans[300000];

int main(){
	int n,K;cin>>n>>K;
	vector<int>vs;
	rep(i,n){
		scanf("%d%d",&a[i],&b[i]);
		vs.push_back(a[i]);
		vs.push_back(b[i]);
	}
	rep(i,K){
		scanf("%d",&t[i]);
		vs.push_back(t[i]);
	}
	sort(vs.begin(),vs.end());
	vs.erase(unique(vs.begin(),vs.end()),vs.end());
	Segtree seg(vs.size());
	rep(i,K){
		int c=lower_bound(vs.begin(),vs.end(),t[i])-vs.begin();
		seg.update(c,i);
	}
	rep(i,n){
		int l=lower_bound(vs.begin(),vs.end(),a[i])-vs.begin();
		int r=lower_bound(vs.begin(),vs.end(),b[i])-vs.begin();
		int id=seg.query(min(l,r),max(l,r));
		if(a[i]<b[i]&&id!=-1)ans[i]=1;
		if(id+1<K)query[id+1].push_back(P(max(l,r),i));
	}
	BIT bit(vs.size());
	for(int i=K-1;i>=0;i--){
		int id=lower_bound(vs.begin(),vs.end(),t[i])-vs.begin();
		bit.add(0,1);
		bit.add(id+1,-1);
		for(P p:query[i]){
			ans[p.second]+=bit.sum(p.first);
		}
	}
	ll sum=0;
	rep(i,n){
		if(ans[i]%2==0)sum+=a[i];
		else sum+=b[i];
	}
	cout<<sum<<endl;
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void BIT::add(int, int)':
fortune_telling2.cpp:39:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(k<bit.size()){
         ~^~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a[i],&b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t[i]);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65