Submission #62042

#	Time	Username	Problem	Language	Result	Execution time	Memory
62042		Mahmoud_Adel	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	7 ms	376 KiB

fortune_telling2

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update


#define f first
#define s second
#define pb push_back
#define mp make_pair
#define clr(dp,i) memset(dp,i,sizeof(dp))
#define opt     ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define inf 0x3f3f3f3f
using namespace std;
using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_t_tag,
//t_order_statistics_node_update> oset;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const long long mod = 1e9+7;
const ld pi = 3.14159265358979323846264338327950288;
//==================================================
const int N = 2e5+1;
ll n, k, q, a[N], b[N], sz[4*N][2];
ll t[4*N][2], mn[4*N][2], mx[4*N][2];
void build(int l, int r, int id)
{
	if(l == r)
	{
		sz[id][0] = a[l];
		sz[id][1] = b[l];
		mn[id][0] = a[l], mx[id][0] = a[l];
		mn[id][1] = b[l], mx[id][1] = b[l];
		return ;
	}
	int mid = (l+r)/2;
	build(l, mid, id*2);
	build(mid+1, r, id*2+1);
	mn[id][0] = min(mn[id*2][0], mn[id*2+1][0]);
	mn[id][1] = min(mn[id*2][1], mn[id*2+1][1]);
	mx[id][0] = max(mx[id*2][0], mx[id*2+1][0]);
	mx[id][1] = max(mx[id*2][1], mx[id*2+1][1]);
	sz[id][0] = sz[id*2][0] + sz[id*2+1][0];
	sz[id][1] = sz[id*2][1] + sz[id*2+1][1];
}
void print(int l, int r, int id)
{
    if(t[id][0])
	{
		t[id][0] = 0;
		swap(mn[id][0], mn[id][1]);
		swap(mx[id][0], mx[id][1]);
		if(l != r)
		t[id*2][0] ^= 1, t[id*2+1][0] ^= 1;
	}
	cout << l << " " << r << endl;
	cout << mx[id][0] << " " << mn[id][0] << " | ";
	cout << mx[id][1] << " " << mn[id][1] << endl;
	if(l == r)
	return ;
	int mid = (l+r)>>1;
	print(l, mid, id*2);
	print(mid+1, r, id*2+1);
}
void query(int l, int r, int id, ll x)
{
	if(t[id][0])
	{
		t[id][0] = 0;
		swap(mn[id][0], mn[id][1]);
		swap(mx[id][0], mx[id][1]);
		swap(sz[id][0], sz[id][1]);
		if(l != r)
		t[id*2][0] ^= 1, t[id*2+1][0] ^= 1;
	}
	if(mn[id][0] > x)
	return;
	if(mx[id][0] <= x)
	{
		swap(mx[id][0], mx[id][1]);
		swap(mn[id][0], mn[id][1]);
		swap(sz[id][0], sz[id][1]);
		if(l != r)
		t[id*2][0] = 1, t[id*2+1][0] = 1;
		return ;
	}
	int mid = (l+r)>>1;
	query(l, mid, id*2, x);
	query(mid+1, r, id*2+1, x);
	mn[id][0] = min(mn[id*2][0], mn[id*2+1][0]);
	mn[id][1] = min(mn[id*2][1], mn[id*2+1][1]);
	mx[id][0] = max(mx[id*2][0], mx[id*2+1][0]);
	mx[id][1] = max(mx[id*2][1], mx[id*2+1][1]);
	sz[id][0] = sz[id*2][0] + sz[id*2+1][0];
	sz[id][1] = sz[id*2][1] + sz[id*2+1][1];
}
int main()
{
	cin >> n >> q;
	for(int i=0; i<n; i++)
	cin >> a[i] >> b[i];
	build(0, n-1, 1);
	//print(0, n-1, 1);
	//cout << sum << endl;
	while(q--)
	{
		ll x;
		cin >> x;
		query(0, n-1, 1, x);
	}
	cout << sz[1][0] << endl;
}

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