Submission #855185

#	Time	Username	Problem	Language	Result	Execution time	Memory
855185		ooscode	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	412 ms	102520 KiB

fortune_telling2

// IN THE NAME OF ALLAH
 
#include<bits/stdc++.h>
 
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define int ll
#define kids int tm = (tl + tr)>>1; int cl = v<<1; int cr = v<<1|1
#define test int n; cin >> n; while(n--)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
 
const int N = 6e5 + 10;
const int K = 800+10;
const ll mod = 998244353;
const ll INF = 1e18+10;
const int P = 31;
const int lg = 25;

int t[N] , q;
int a[N] , b[N] , n;
int A[N] , B[N];
int rmq[3*N][lg];
int ty[N] , tim[N];
vector<int> qu[N];

int seg[N << 2];
int la[N << 2];

void init() {
	for(int i = 1 ; i < lg ; i++)
		for(int j = 1 ; j <= q ; j++) {
			if(q-j+1 < (1ll << i))
				continue;
			
			rmq[j][i] = max(rmq[j][i-1] , rmq[j + (1ll << (i-1))][i-1]);
		}
}

int ask_rmq(int l , int r) {
	int x = log2(r-l+1);
	return max(rmq[l][x] , rmq[r - (1ll << x) + 1][x]);
}

void shift(int v , int tl , int tr) {
	if(la[v] == 0)
		return;

	seg[v] ^= 1;
	if(tl != tr)
		la[v << 1] ^= 1 , la[v << 1 | 1] ^= 1;

	la[v] = 0;
}

void upd(int v , int tl , int tr , int l , int r) {
	shift(v , tl , tr);
	if(l > r)
		return;
	if(tl == l && tr == r) {
		la[v] ^= 1;
		shift(v , tl , tr);
		return;
	}

	kids;

	upd(cl , tl , tm , l , min(tm , r));
	upd(cr , tm+1 , tr , max(tm+1 , l) , r);
}

void fix(int v , int tl , int tr , int pos , int x) {
	shift(v , tl , tr);
	if(tl == tr) {
		seg[v] = x;
		return;
	}

	kids;
	if(tm >= pos)
		fix(cl , tl , tm , pos , x);
	else
		fix(cl , tm+1 , tr , pos , x);
}

int ask(int v , int tl , int tr , int pos) {
	shift(v , tl , tr);
	if(tl == tr) 
		return seg[v];
	kids;
	if(tm >= pos)
		return ask(cl , tl , tm , pos);
	return ask(cr , tm+1 , tr , pos);
}

void solve() {
	cin >> n >> q;

	vector<pair<int , pii>> vec;

	for(int i = 1 ; i <= n ; i++) {
		cin >> a[i] >> b[i]; 
		vec.pb({max(a[i] , b[i]) , {a[i] , b[i]}});
	}

	vec.pb({-INF , {-INF , -INF}});
	sort(all(vec));

	for(int i = 1 ; i <= n ; i++)
		a[i] = vec[i].S.F , b[i] = vec[i].S.S;

	// wall;
	// cout << "check0 :\n";
	// for(int i = 1 ; i <= n ; i++)
	// 	cout << a[i] << " " << b[i] << "\n";
	// wall;

	vector<pii> ve; 

	for(int i = 1 ; i <= q ; i++) {
		cin >> t[i];
		ve.pb({t[i] , i});
	}

	ve.pb({-INF , -INF});
	sort(all(ve));

	for(int i = 1 ; i <= q ; i++)
		rmq[i][0] = ve[i].S; 
	init();

	for(int i = 1 ; i <= n ; i++) {
		if(a[i] == b[i])
			continue;

		int x = a[i] , y = b[i];
		if(x > y)
			swap(x , y);

		ty[i] = 0;
		if(a[i] < b[i]) ty[i] = 1;

		int l = -1 , r = q+1;
		if(ve[q].F >= x)
			l = lower_bound(all(ve) , make_pair(x , -INF)) - ve.begin();
		if(ve[q].F >= y)
			r = lower_bound(all(ve) , make_pair(y , -INF)) - ve.begin();
		r--;

		if(l == -1 || r == 0 || l > r)
			continue;
		
		tim[i] = ask_rmq(l , r);
		qu[tim[i]].pb(i);
	}

	// wall;
	// cout << "check1 :\n";
	// for(int i = 1 ; i <= n ; i++) {
	// 	cout << i << " " << ty[i] << " " << tim[i] << "\n";
	// }
	// wall;
	// cout << "check2 :\n";
	// for(int i = 1 ; i <= q ; i++) {
	// 	cout << i << " :\n";
	// 	for(auto u : qu[i])
	// 		cout << u << " " << ty[u] << "\n";
	// }
	// wall;

	for(int i = 1 ; i <= q ; i++) {
		auto it = lower_bound(all(vec) , make_pair(t[i]+1 , make_pair(-INF , -INF)));
		int ind = n;

		if(it != vec.end())
			ind = it - vec.begin() - 1;

		upd(1 , 1 , n , 1 , ind);

		// cout << "id = " << ind << " : ";

		for(auto u : qu[i]) {
			int x = ask(1 , 1 , n , u);
			// cout << x << " - ";
			if(x != ty[u])
				upd(1 , 1 , n , u , u);
		}

		// cout << "\n";
	}

	int ans = 0;

	for(int i = 1 ; i <= n ; i++) 
		ans += (ask(1 , 1 , n , i) == 1 ? b[i] : a[i]);

	cout << ans << "\n";
}

signed main()
{   
	solve();
} 

// IT'S EASY TO SEE
// CODE = LOVE

Compilation message (stderr)

fortune_telling2.cpp: In function 'void fix(ll, ll, ll, ll, ll)':
fortune_telling2.cpp:14:56: warning: unused variable 'cr' [-Wunused-variable]
   14 | #define kids int tm = (tl + tr)>>1; int cl = v<<1; int cr = v<<1|1
      |                                                        ^~
fortune_telling2.cpp:91:2: note: in expansion of macro 'kids'
   91 |  kids;
      |  ^~~~

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