Submission #714701

#	Time	Username	Problem	Language	Result	Execution time	Memory
714701		dsyz	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	174 ms	262144 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node1{
	ll s, e, m, val, lazy;
	node1 *l, *r;
	node1(ll S, ll E){
		s = S, e = E, m = (s+e)/2;
		val = 0;
		lazy = 0;
		if(s != e){
			l = new node1(s,m);
			r = new node1(m + 1,e);
		}
	}
	void propogate(){
		if(lazy==0) return;
		val = max(val,lazy);
		if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement)
			l->lazy = max(l -> lazy,lazy);
			r->lazy = max(r -> lazy,lazy);
		}
		lazy = 0;
	}
	void update(int S, int E, ll V){
		if(s == S && e == E) lazy = max(lazy,V);
		else{
			if(E <= m) l->update(S, E, V);
			else if (m < S) r->update(S, E, V);
			else l->update(S, m, V),r->update(m+1, E, V);
			l->propogate(),r->propogate();
			val = max(l->val,r->val);
		}
	}
	ll query(int S, int E){
		propogate(); //remember to propogate
		if(s == S && e == E) return val; 
		else if(E <= m) return l->query(S, E); 
		else if(S >= m+1) return r->query(S, E);
		else return max(l->query(S, m),r->query(m+1, E));
	}
} *root1;
struct node{
	ll s, e, m, val, lazy;
	node *l, *r;
	node(ll S, ll E){
		s = S, e = E, m = (s+e)/2;
		val = 0;
		lazy = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propogate(){
		if(lazy==0) return;
		val += lazy*(e-s+1);
		if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement)
			l->lazy += lazy;
			r->lazy += lazy;
		}
		lazy = 0;
	}
	void update(int S, int E, ll V){
		if(s == S && e == E) lazy += V;
		else{
			if(E <= m) l->update(S, E, V);
			else if (m < S) r->update(S, E, V);
			else l->update(S, m, V),r->update(m+1, E, V);
			l->propogate(),r->propogate();
			val = l->val + r->val;
		}
	}
	ll query(int S, int E){
		propogate(); //remember to propogate
		if(s == S && e == E) return val; 
		else if(E <= m) return l->query(S, E); 
		else if(S >= m+1) return r->query(S, E);
		else return l->query(S, m) + r->query(m+1, E); 
	}
} *root2;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,K;
	cin>>N>>K;
	root1 = new node1(0,MAXN);
	root2 = new node(0,MAXN);
	ll A[N], B[N], a[N], b[N];
	vector<ll> d;
	for(ll i = 0;i < N;i++){
		cin>>A[i]>>B[i];
		a[i] = A[i];
		b[i] = B[i];
		d.push_back(A[i]);
		d.push_back(B[i]);
	}
	ll T[K];
	for(ll i = 0;i < K;i++){
		cin>>T[i];
		d.push_back(T[i]);
	}
	sort(d.begin(),d.end());
	d.resize(unique(d.begin(),d.end()) - d.begin());
	for(ll i = 0;i < N;i++){
		A[i] = lower_bound(d.begin(),d.end(),A[i]) - d.begin();
		B[i] = lower_bound(d.begin(),d.end(),B[i]) - d.begin();
	}
	for(ll i = 0;i < K;i++){
		T[i] = lower_bound(d.begin(),d.end(),T[i]) - d.begin();
	}
	vector<ll> v[MAXN]; //stores the i
	for(ll i = 0;i < N;i++){
		v[A[i]].push_back(i);
		v[B[i]].push_back(i);
	}
	for(ll k = 0;k < K;k++){
		root1 -> update(T[k],T[k],k + 1); //k is 1-indexed
	}
	vector<ll> start11[MAXN];
	ll side[N];
	memset(side,0,sizeof(side));
	for(ll i = 0;i < N;i++){
		if(A[i] == B[i]){
			start11[0].push_back(i);
			side[i] = 0;
			continue;
		}
		ll num = root1 -> query(min(A[i],B[i]),max(A[i],B[i]) - 1);
		num--;
		if(num >= 0){
			start11[num + 1].push_back(i);
			if(A[i] < B[i]) side[i] = 1;
			else side[i] = 0;
		}else{
			start11[0].push_back(i);
			side[i] = 0;
		}
	}
	deque<pair<ll,ll> > dq;
	for(ll i = 0;i < K;i++){
		dq.push_back({T[i],i});
	}
	sort(dq.begin(),dq.end(),greater<pair<ll,ll> >());
	ll numof11[N];
	memset(numof11,0,sizeof(numof11));
	for(ll i = K - 1;i >= 0;i--){
		while(!dq.empty() && dq.front().second >= i){
			root2 -> update(dq.front().first,dq.front().first,1);
			dq.pop_front();
		}
		for(auto u : start11[i]){
			numof11[u] = root2 -> query(max(A[u],B[u]),MAXN);
		}
	}
	ll sum = 0;
	for(ll i = 0;i < N;i++){
		if(side[i] == 0){
			if(numof11[i] % 2 == 1) sum += b[i];
			else sum += a[i];
		}else if(side[i] == 1){
			if(numof11[i] % 2 == 0) sum += a[i];
			else sum += b[i];
		}
	}
	cout<<sum<<'\n';
}

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