Submission #758080

#	Time	Username	Problem	Language	Result	Execution time	Memory
758080		PoPularPlusPlus	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	234 ms	17720 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

struct Seg {
	int siz;
	vector<int> mx;
	
	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		
		mx.assign(siz * 2 , -1);
	}
	
	void build(vector<int>& a , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < a.size())mx[x] = a[lx];
			return;
		}
		int m = (lx + rx)/2;
		build(a , 2 * x + 1 , lx , m);
		build(a , 2 * x + 2 , m , rx);
		mx[x] = max(mx[2 * x + 1] , mx[2 * x + 2]);
	}
	
	void build(vector<int>& a){
		build(a , 0 , 0 , siz);
	}
	
	int range_mx(int l , int r , int x , int lx ,int rx){
		if(r <= lx || rx <= l)return -1;
		if(lx >= l && rx <= r)return mx[x];
		int m = (lx + rx)/2;
		return max(range_mx(l , r , 2 * x + 1 , lx , m) , range_mx(l , r , 2 * x + 2 , m ,rx));
	}
	
	int range_mx(int l , int r){
		return range_mx(l , r , 0 , 0 , siz);
	}
};

struct Fen {
	vector<int> tree;
	int n;
	
	void init(int n1){
		n = n1;
		tree.assign(n + 1 , 0);
	}
	
	void set(int i){
		i++;
		while(i <= n){
			tree[i]++;
			i += (i & -i);
		}
	}
	
	int sum(int i){
		i++;
		int res = 0;
		while(i > 0){
			res += tree[i];
			i -= (i & -i);
		}
		return res;
	}
};

void solve(){
	int n , k;
	cin >> n >> k;
	int arr[n][2];
	for(int i = 0; i < n; i++)cin >> arr[i][0] >> arr[i][1];
	vector<pair<int,int>> q;
	for(int i = 0; i < k; i++){
		int x;
		cin >> x;
		q.pb(mp(x,i));
	}
	sort(all(q));
	vector<int> a,b;
	for(int i = 0; i < k; i++){
		if(i == k - 1 || q[i+1].vf != q[i].vf){
			a.pb(q[i].vf);
			b.pb(q[i].vs);
		}
	}
	Seg st;
	st.init(b.size() + 1);
	st.build(b);
	
	//cout << "came" << endl;
	
	int pos[n];
	ll res = 0;
	for(int i = 0; i < n; i++){
		if(arr[i][0] == arr[i][1]){
			res += arr[i][0];
			continue;
		}
		int l = lower_bound(all(a),min(arr[i][0],arr[i][1])) - a.begin();
		int r = lower_bound(all(a),max(arr[i][0],arr[i][1])) - a.begin();
		if(l == r){
			pos[i] = -1;
		}
		else pos[i] = st.range_mx(l , r);
	}
	
	vector<pair<int,int>> v;
	for(int i = 0; i < n; i++){
		if(arr[i][0] != arr[i][1])v.pb(mp(max(arr[i][0] , arr[i][1]),i));
	}
	
	sort(all(v),greater<>());
		
	Fen ft;
	ft.init(k + 1);
	
	int j = q.size() - 1;
	int cnt = 0;
	
	for(int i = 0; i < v.size(); i++){
		while(j >= 0 && q[j].vf >= v[i].vf){
			ft.set(q[j].vs);
			j--;
			cnt++;
		}
		int idx = v[i].vs;
		if(pos[idx] == k-1){
			//cout << v[i].vf << ' ';
			res += v[i].vf;
			continue;
		}
		if(pos[idx] == -1){
			if(cnt % 2 == 0){
				res += arr[idx][0];
				//cout << arr[idx][0] << ' ';
			}
			else {
				res += arr[idx][1];
				//cout << arr[idx][1] << ' ';
			}
			continue;
		}
		int sub = ft.sum(pos[idx]);
		//cout << "sub " << sub << ' ';
		if((cnt - sub) % 2 == 0){
			//cout << v[i].vf << ' ';
			res += v[i].vf;
		}
		else {
			res += min(arr[idx][0] , arr[idx][1]);
			//cout << min(arr[idx][0] , arr[idx][1]) << ' ';
		}
	}
	
	cout << res << '\n';
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void Seg::build(std::vector<int>&, int, int, int)':
fortune_telling2.cpp:37:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    if(lx < a.size())mx[x] = a[lx];
      |       ~~~^~~~~~~~~~
fortune_telling2.cpp: In function 'void solve()':
fortune_telling2.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~

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