Submission #109099

#	Time	Username	Problem	Language	Result	Execution time	Memory
109099		Diuven	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	402 ms	12696 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 2e5+10;
const int MX2 = (1<<19);
const lint LNF = 2e18;

const int _max(int a, int b){ return a>b ? a : b; }

class Crd_t{
	vector<int> P;
  public:
	void add(int p){
		P.push_back(p);
	}
	int compress(){
		sort(P.begin(), P.end());
		int sz = unique(P.begin(), P.end()) - P.begin();
		P.resize(sz);
		return sz;
	}
	int get_lo(int x){
		return upper_bound(P.begin(), P.end(), x) - P.begin() -1 + 1;
	}
	int get(int x){
		if(!binary_search(P.begin(), P.end(), x)){ cerr<<"SHIT\n"; exit(42); }
		return get_lo(x);
	}
} Crd;

class Seg1_t{
	// max
	vector<int> T;
	int n;
	void add(int v, int s, int e, int p, int x){
		T[v] = _max(T[v], x);
		if(s==e) return;
		int mid = (s+e)/2;
		if(p<=mid) add(v*2,s,mid,p,x);
		else add(v*2+1,mid+1,e,p,x);
	}
	int get(int v, int s, int e, int l){
		if(l<=s) return T[v];
		if(e<l) return 0;
		return _max(get(v*2,s,(s+e)/2,l), get(v*2+1,(s+e)/2+1,e,l));
	}
  public:
	void init(int sz){
		n = sz;
		T.resize(MX2, 0);
	}
	void add(int x, int val){
		x = Crd.get_lo(x);
		add(1,1,n,x,val);
	}
	int get(int x){
		x = Crd.get(x);
		return get(1,1,n,x);
	}
} Seg1;

class Seg2_t{
	// sum
	vector<int> T;
	int n;
	void add(int v, int s, int e, int p, int x){
		T[v]++;
		if(s==e) return;
		int mid = (s+e)/2;
		if(p<=mid) add(v*2,s,mid,p,x);
		else add(v*2+1,mid+1,e,p,x);
	}
	int get(int v, int s, int e, int l){
		if(l<=s) return T[v];
		if(e<l) return 0;
		return get(v*2,s,(s+e)/2,l) + get(v*2+1,(s+e)/2+1,e,l);
	}
  public:
	void init(int sz){
		n = sz;
		T.resize(MX2, 0);
	}
	void add(int idx, int val){
		add(1,1,n,idx,val);
	}
	int get(int x){
		return get(1,1,n,x);
	}
} Seg2;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	int n, k; cin>>n>>k;
	static int A[MAX], B[MAX];
	vector<pii> P, Q;

	for(int i=1; i<=n; i++){
		int a, b; cin>>a>>b;
		A[i] = a, B[i] = b;
		P.push_back({max(a,b), i});
		Crd.add(min(a,b));
	}
	for(int i=1; i<=k; i++){
		int t; cin>>t;
		Q.push_back({t, i});
	}

	sort(Q.begin(), Q.end());
	sort(P.begin(), P.end());

	Crd.add(0);
	int sz = Crd.compress();
	Seg1.init(sz); Seg2.init(k);

	// max, sum

	for(pii q:Q){
		int t,i; tie(t,i) = q;
		Seg2.add(i, 1);
	}

	lint ans = 0;

	for(pii p:P){
		int c,i; tie(c,i) = p;
		static int frt = 0;
		while(frt<k && Q[frt].first < c){
			int t,j; tie(t,j) = Q[frt++];
			Seg2.add(j, -1);
			Seg1.add(t, j);
		}

		int d = min(A[i], B[i]);
		int x = Seg1.get(d);
		int y = Seg2.get(x+1);
		if(x<=0) ans += (y%2 ? B[i] : A[i]);
		else 	 ans += (y%2 ? d : c);
	}

	cout<<ans<<'\n';

	return 0;
}

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