oj.uz

Submission #855185

# Submission time Handle Problem Language Result Execution time Memory
855185 2023-09-30T13:23:27 Z ooscode Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 412 ms 102520 KB 
// 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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29276 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 6 ms 29124 KB Output is correct
11 Correct 6 ms 29276 KB Output is correct
12 Correct 7 ms 29276 KB Output is correct
13 Correct 6 ms 29276 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29276 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 6 ms 29124 KB Output is correct
11 Correct 6 ms 29276 KB Output is correct
12 Correct 7 ms 29276 KB Output is correct
13 Correct 6 ms 29276 KB Output is correct
14 Correct 21 ms 34392 KB Output is correct
15 Correct 45 ms 37324 KB Output is correct
16 Correct 54 ms 41928 KB Output is correct
17 Correct 71 ms 45304 KB Output is correct
18 Correct 71 ms 43968 KB Output is correct
19 Correct 66 ms 43968 KB Output is correct
20 Correct 71 ms 44052 KB Output is correct
21 Correct 69 ms 44300 KB Output is correct
22 Correct 54 ms 43716 KB Output is correct
23 Correct 56 ms 44736 KB Output is correct
24 Correct 58 ms 44740 KB Output is correct
25 Correct 52 ms 43672 KB Output is correct
26 Correct 59 ms 43712 KB Output is correct
27 Correct 83 ms 45172 KB Output is correct
28 Correct 67 ms 45252 KB Output is correct
29 Correct 71 ms 45264 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29276 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 6 ms 29124 KB Output is correct
11 Correct 6 ms 29276 KB Output is correct
12 Correct 7 ms 29276 KB Output is correct
13 Correct 6 ms 29276 KB Output is correct
14 Correct 21 ms 34392 KB Output is correct
15 Correct 45 ms 37324 KB Output is correct
16 Correct 54 ms 41928 KB Output is correct
17 Correct 71 ms 45304 KB Output is correct
18 Correct 71 ms 43968 KB Output is correct
19 Correct 66 ms 43968 KB Output is correct
20 Correct 71 ms 44052 KB Output is correct
21 Correct 69 ms 44300 KB Output is correct
22 Correct 54 ms 43716 KB Output is correct
23 Correct 56 ms 44736 KB Output is correct
24 Correct 58 ms 44740 KB Output is correct
25 Correct 52 ms 43672 KB Output is correct
26 Correct 59 ms 43712 KB Output is correct
27 Correct 83 ms 45172 KB Output is correct
28 Correct 67 ms 45252 KB Output is correct
29 Correct 71 ms 45264 KB Output is correct
30 Correct 172 ms 78408 KB Output is correct
31 Correct 213 ms 82480 KB Output is correct
32 Correct 265 ms 88024 KB Output is correct
33 Correct 396 ms 102212 KB Output is correct
34 Correct 100 ms 75192 KB Output is correct
35 Correct 379 ms 101248 KB Output is correct
36 Correct 389 ms 100792 KB Output is correct
37 Correct 412 ms 102428 KB Output is correct
38 Correct 355 ms 100788 KB Output is correct
39 Correct 375 ms 100536 KB Output is correct
40 Correct 298 ms 100188 KB Output is correct
41 Correct 348 ms 100812 KB Output is correct
42 Correct 381 ms 102520 KB Output is correct
43 Correct 258 ms 98644 KB Output is correct
44 Correct 263 ms 99380 KB Output is correct
45 Correct 257 ms 100828 KB Output is correct
46 Correct 305 ms 98484 KB Output is correct
47 Correct 339 ms 98748 KB Output is correct
48 Correct 346 ms 100276 KB Output is correct
49 Correct 349 ms 100284 KB Output is correct