Submission #364863

#	Time	Username	Problem	Language	Result	Execution time	Memory
364863		Bill_00	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	112 ms	30568 KiB

fortune_telling2

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define N 200001
typedef long long ll;
const long long MOD=1000000007;
using namespace std;
ll n,k;
ll a[N],b[N],mx[4*N+4];
pair<ll,ll>t[N];
vector<ll>v[4*N+4];
void build(ll id,ll l,ll r){
	if(l==r){
		v[id].pb(-t[l].ss);
		mx[id]=t[l].ss;
		return;
	}
	ll m=l+r>>1;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	mx[id]=max(mx[id*2],mx[id*2+1]);
	ll i=0,j=0;
	while(i<v[id*2].size() && j<v[id*2+1].size()){
		if(v[id*2][i]<v[id*2+1][j]){
			v[id].pb(v[id*2][i]);
			i++;
		}
		else{
			v[id].pb(v[id*2+1][j]);
			j++;
		}
	}
	while(i<v[id*2].size()){
		v[id].pb(v[id*2][i]);
		i++;
	}
	while(j<v[id*2+1].size()){
		v[id].pb(v[id*2+1][j]);
		j++;
	}
}
ll query1(ll id,ll l,ll r,ll L,ll R){
	if(r<L || R<l) return 0;
	if(L<=l && r<=R) return mx[id];
	ll m=(l+r)>>1;
	return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
ll query2(ll id,ll l,ll r,ll L,ll R,ll k){

		// cout << v[id].size() << ' ' << l << ' ' << r << '\n';
	if(r<L || R<l) return 0;
	if(L<=l && r<=R){
		return (lower_bound(v[id].begin(),v[id].end(),-k)-v[id].begin());
	}

	ll m=(l+r)>>1;
	return (query2(id*2,l,m,L,R,k)+query2(id*2+1,m+1,r,L,R,k));
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(ll i=1;i<=n;i++){
		cin >> a[i] >> b[i];
	}
	for(ll i=1;i<=k;i++){
		cin >> t[i].ff;
		t[i].ss=i;
	}
	sort(t+1,t+k+1);
	build(1,1,k);
	ll ans=0;
	for(ll i=1;i<=n;i++){
		pair<ll,ll>temp={min(a[i],b[i]),0};
		ll l=(lower_bound(t+1,t+k+1,temp)-(t+1));
		l++;
		temp={max(a[i],b[i]),0};
		ll r=(lower_bound(t+1,t+k+1,temp)-(t+1));
		if(l>r){
			ans+=(((n-r)%2)?b[i]:a[i]);
		}
		else{
			ll p=query1(1,1,k,l,r);
			ll u=query2(1,1,k,r+1,k,p);
			// cout << r << " SKKSK" << ' ';
			ans+=((u%2)?min(a[i],b[i]):max(a[i],b[i]));
		}
	}
	cout << ans;

}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void build(ll, ll, ll)':
fortune_telling2.cpp:19:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |  ll m=l+r>>1;
      |       ~^~
fortune_telling2.cpp:24:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  while(i<v[id*2].size() && j<v[id*2+1].size()){
      |        ~^~~~~~~~~~~~~~~
fortune_telling2.cpp:24:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  while(i<v[id*2].size() && j<v[id*2+1].size()){
      |                            ~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:34:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while(i<v[id*2].size()){
      |        ~^~~~~~~~~~~~~~~
fortune_telling2.cpp:38:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  while(j<v[id*2+1].size()){
      |        ~^~~~~~~~~~~~~~~~~

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