제출 #1158418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158418		Nurislam	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	386 ms	93316 KiB

fortune_telling2

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

const int N = 2e5+2, inf = 1e18;

struct segt{
	vector<int> t, sm;
	int n;
	segt(int n) : n(n){
		t.resize(n*4);
		sm.resize(n*4);
	};
	
	void upd(int ps, int va, int i, int l, int r) {
		if(l == r) {
			t[i] = max(t[i], va);
			sm[i] ++;
			return;
		};
		int m = (l + r) >> 1;
		if(ps <= m)upd(ps, va, i << 1, l, m);
		else upd(ps, va, i << 1 | 1, m + 1, r);
		
		t[i] = max( t[i << 1], t[i << 1 | 1] );
		sm[i] = sm[i << 1] + sm[i << 1 | 1];
	};
	
	void upd(int ps, int va) {
		upd(ps, va, 1, 0, n);
	};
	
	int getm(int tl, int tr, int i, int l, int r) {
		if(l > tr || r < tl)return 0;
		if(tl <= l && r <= tr)return t[i];
		
		int m = (l + r) >> 1;
		
		return max( getm(tl, tr, i << 1, l, m), 
			getm(tl, tr, i << 1 | 1, m + 1, r) );
	};
	
	int getm(int tl, int tr){
		if(tl > tr)return 0;
		return getm(tl, tr, 1, 0, n);
	};
	
	
	int gets(int tl, int tr, int i, int l, int r) {
		if(l > tr || r < tl)return 0;
		if(tl <= l && r <= tr)return sm[i];
		
		int m = (l + r) >> 1;
		
		return gets(tl, tr, i << 1, l, m) +
			gets(tl, tr, i << 1 | 1, m + 1, r);
	};
	
	int gets(int tl, int tr){
		if(tl > tr)return 0;
		return gets(tl, tr, 1, 0, n);
	};
};

void solve(){
	int n, k;
	cin >> n >> k;
	vector<int> a(n), b(n), la(n);
	
	for(int i = 0; i < n; i ++ )
		cin >> a[i] >> b[i];
	vector<int> _a = a, _b = b;
		
	vector<int> t(k);
	for(int &i : t)cin >> i;
	
	auto compres = [&](){
		vector<int> res{0};
		for(int i : a)res.push_back(i);
		for(int i : b)res.push_back(i);
		for(int i : t)res.push_back(i);
		
		sort(res.begin(), res.end());
		res.erase(unique(res.begin(), res.end()), res.end());
		
		for(int &i : a) i = lower_bound(res.begin(), res.end(), i) - res.begin();
		for(int &i : b) i = lower_bound(res.begin(), res.end(), i) - res.begin();
		for(int &i : t) i = lower_bound(res.begin(), res.end(), i) - res.begin();
	};compres();
	
	//for(int i = 0; i < n; i ++ ) cout << a[i] << ' ' << b[i] << '\n';
	//for(int i : t)cout << i << '\n';
	
	int sz = n*2 + k + 5;
	segt tr(sz + 5);
	for(int i = 1; i <= k; i ++ ) 
		tr.upd(t[i-1], i);
	
	
	vector<vector<int>> ps( k + 1 );
	for(int i = 0; i < n; i ++ ){
		if( a[i] <= b[i] ) {
			ps[tr.getm(a[i], b[i]-1)].push_back(i);
			//cout << tr.getm(a[i], b[i]-1) << ' ';
		}else{
			ps[tr.getm(b[i], a[i]-1)].push_back(i);
			//cout << tr.getm(b[i], a[i]-1) << ' ';
		};
	};
	//cout << '\n';
	
	tr = segt(sz + 5);

	//for(int i = 1; i <= 8; i ++ )cout << tr.gets(i, i) << ' ';
	//cout << '\n';
	vector<int> cnt(n);
	for(int i = k; i >= 1; i -- ) {
		tr.upd(t[i-1], 0);
		//cout << t[i-1] << ' ';
		//for(int i = 1; i <= 8; i ++ )cout << tr.gets(i, i) << ' ';
		//cout << '\n';
		for(int j : ps[i]) {
			cnt[j] = tr.gets(max(a[j], b[j]), sz);
			if(a[j] <= b[j]) cnt[j] ++; 
		}
	};
	for(int j : ps[0]) {
		cnt[j] = tr.gets(max(a[j], b[j]), sz);
	};
	
	for(int i = 0; i <= k; i ++ ) {
		//cout << i << " : \n";
		//for(int j : ps[i])cout << j << ' ';
		//cout << '\n';
	};
	//for(int i = 0; i < n; i ++ ) cout << cnt[i] << ' ';
	//cout << '\n';
	
	int ans = 0;
	for(int i = 0; i < n; i ++ ) {
		if(cnt[i] % 2 == 0)ans += _a[i];
		else ans += _b[i];
	};
	cout << ans << '\n';	
};
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while(tt--){
        solve();
    };
};

 
 

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