Submission #656575

#	Time	Username	Problem	Language	Result	Execution time	Memory
656575		mousey	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	3049 ms	59600 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define vi vector <int>
#define vip vector <pair <int, int> >
#define db double
#define ld long double
#define pdb pair <double, double> 
#define YES cout<<"YES"
#define NO cout<<"NO"
#define nl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll> 
#define pi pair <int, int>
#define pb push_back
#define f first
#define s second
using namespace std;

const ll mod=1e9+7;
const ll modx=998244353;
const ld eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=1e18;
const ll N=2e5;
int n, q;
vip v;

void input()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
    	int x, y;
    	cin >> x >> y;
    	v.pb({x, y});
	}
}

struct Node{
	vi x, y; 
	int lazy, x_max, x_min, y_max, y_min;
};

Node st[4*N+5];

void Nodeupdate(int id)
{
    st[id].x.clear();
	st[id].y.clear();
	for(int i = id*2; i <= id*2+1; i++)
	{
		for(auto j: st[i].x) st[id].x.pb(j);
		for(auto j: st[i].y) st[id].y.pb(j);
	}
	st[id].x_max=max(st[id*2].x_max, st[id*2+1].x_max);
	st[id].y_max=max(st[id*2].y_max, st[id*2+1].y_max);
	st[id].x_min=min(st[id*2].x_min, st[id*2+1].x_min);
	st[id].y_min=min(st[id*2].y_min, st[id*2+1].y_min);
}

void build(int l, int r, int id)
{
	st[id].lazy=0;
	if(l==r)
	{
	    st[id].x.clear();
	    st[id].y.clear();
		st[id].x.pb(v[l-1].f);
		st[id].y.pb(v[l-1].s);
		st[id].x_max=v[l-1].f;
		st[id].x_min=v[l-1].f;
		st[id].y_max=v[l-1].s;
		st[id].y_min=v[l-1].s;
		return;
	}
	int mid=(l+r)/2;
	build(l, mid, id*2);
	build(mid+1, r, id*2+1);
	Nodeupdate(id);
}

void Nodeswap(int id)
{
	swap(st[id].x, st[id].y);
	swap(st[id].x_min, st[id].y_min);
	swap(st[id].x_max, st[id].y_max);
}

void push(int id)
{
	st[id*2].lazy^=1;
	st[id*2+1].lazy^=1;
}

void update(int l, int r, int id, int val)
{
//    cout << l << " " << r << " " << id << "\n";
//    cout << st[id].x_min << " " << st[id].x_max << "\n";
	if(st[id].lazy)
	{
		Nodeswap(id);
		if(l!=r) push(id);
		st[id].lazy=0;
	}
	if(st[id].x_min>val) return;
	else if(st[id].x_max<=val)
	{
		Nodeswap(id);
		if(l!=r) push(id);
		return;
	}
	int mid=(l+r)/2;
	update(l, mid, id*2, val);
	update(mid+1, r, id*2+1, val);
	Nodeupdate(id);
}

void query()
{
	if(st[1].lazy) Nodeswap(1);
	for(int i = 0; i < n; i++) v.pb({st[1].x[i], st[1].y[i]});
}

void solve()
{
    int block_size=1000;
    sort(v.begin(), v.end());
    build(1, n, 1);
    for(int i = 1; i <= q; i++)
    {
    	int l;
    	cin >> l;
    	if(i%block_size==0)
    	{
    		v.clear();
    		query();
    		sort(v.begin(), v.end());
    		build(1, n, 1);
		}
		update(1, n, 1, l);
	}
	v.clear();
	query();
	ll ans=0;
	for(auto i: v) ans+=i.f;
	cout << ans;
}

signed main() 
{
//	auto start_time = chrono::high_resolution_clock::now();
//	freopen("SHOPPING.inp", "r", stdin);
//	freopen("SHOPPING.out", "w", stdout);
    srand(time(0));
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int t=1;
//	cin >> t;
	for(int i = 1; i <= t; i++)
	{
		input();
	    solve();
	    nl;
	}
//    auto end_time = chrono::high_resolution_clock::now();
//        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
//        cout << "\n[ " << duration << " ms ]\n"; 
}

/*
7 3
4 6 8 2 10 5 1
6 1 1000000000 17
4 1 1000000000 17
1 1 1000000000 17
*/

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