Submission #899505

#	Time	Username	Problem	Language	Result	Execution time	Memory
899505		Batorgil952	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1187 ms	128688 KiB

fortune_telling2

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

const ll N=2e5+5;
ll a[N], b[N], T[N], A[N], B[N];
map< ll, ll > M;
ll tree[12*N], ma[12*N];
vector< pair< ll, ll > > u[6*N];

void update(ll v, ll l, ll r, ll x, ll p){
	if(l==x && x==r) tree[v]=p;
	else if(l<=x && x<=r){
		ll mid=(l+r)/2;
		update(2*v, l, mid, x, p);
		update(2*v+1, mid+1, r, x, p);
		tree[v]=max(tree[2*v], tree[2*v+1]);
	}
	else{
		return;
	}
}

ll query(ll v, ll l, ll r, ll ql, ll qr){
	if(r<ql || qr<l) return 0;
	if(ql<=l && r<=qr){
		return tree[v];
	}
	ll mid=(l+r)/2;
	return max(query(2*v, l, mid, ql, qr), query(2*v+1, mid+1, r, ql, qr));
}

void update1(ll v, ll l, ll r, ll p){
	if(l==p && p==r) ma[v]++;
	else if(l<=p && p<=r){
		ll mid=(l+r)/2;
		update1(2*v, l, mid, p);
		update1(2*v+1, mid+1, r, p);
		ma[v]=ma[2*v]+ma[2*v+1];
	}
	else return;
}

ll query1(ll v, ll l, ll r, ll p){
	if(p<=l) return ma[v];
	if(r<p) return 0;
	ll mid=(l+r)/2;
	return query1(2*v, l, mid, p)+query1(2*v+1, mid+1, r, p);
}

int main(){
	ll t, n, i, q, vn, ans, p, s, j;
	vector< ll > v;
	
	scanf("%lld",&n);
	scanf("%lld",&q);
	for(i=1; i<=n; i++){
		scanf("%lld",&a[i]);
		scanf("%lld",&b[i]);
		v.pb(a[i]);
		v.pb(b[i]);
	}
	
	for(i=1; i<=q; i++){
		scanf("%lld",&T[i]);
		v.pb(T[i]);
	}
	
	sort(v.begin(), v.end());
	s=1;
	M[v[0]]=1;
	vn=v.size();
	for(i=1; i<vn; i++){
		if(v[i]!=v[i-1]){
			s++;
			M[v[i]]=s;
		}
	}
	for(i=1; i<=n; i++){
		A[i]=a[i];
		B[i]=b[i];
		a[i]=M[a[i]];
		b[i]=M[b[i]];
	}
	for(i=1; i<=q; i++){
		T[i]=M[T[i]];
		update(1, 1, s, T[i], i);
	}
	
	ans=0;
	for(i=1; i<=n; i++){
		if(a[i]==b[i]){
			ans+=A[i];
			continue;
		}
		p=query(1, 1, s, min(a[i], b[i]), max(a[i], b[i])-1);
		u[p].pb(mp(max(a[i], b[i]), i));
	}
	
	for(i=q; i>=0; i--){
		if(i!=0) update1(1, 1, s, T[i]);
		vn=u[i].size();
		for(j=0; j<vn; j++){
			if(query1(1, 1, s, u[i][j].ff)%2==0){
				if(i!=0) ans+=max(A[u[i][j].ss], B[u[i][j].ss]);
				else{
					ans+=A[u[i][j].ss];
				}
			}
			else{
				if(i!=0) ans+=min(A[u[i][j].ss], B[u[i][j].ss]);
				else{
					ans+=B[u[i][j].ss];
				}
			}
		}
	}
	
	printf("%lld\n", ans);
	
	
	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:57:5: warning: unused variable 't' [-Wunused-variable]
   57 |  ll t, n, i, q, vn, ans, p, s, j;
      |     ^
fortune_telling2.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
fortune_telling2.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%lld",&q);
      |  ~~~~~^~~~~~~~~~~
fortune_telling2.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%lld",&a[i]);
      |   ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%lld",&b[i]);
      |   ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%lld",&T[i]);
      |   ~~~~~^~~~~~~~~~~~~~

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