oj.uz

Submission #656579

# Submission time Handle Problem Language Result Execution time Memory
656579 2022-11-08T02:00:48 Z mousey Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 3000 ms 59392 KB 
#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()
{
    sort(v.begin(), v.end());
    build(1, n, 1);
    for(int i = 1; i <= q; i++)
    {
    	int l;
    	cin >> l;
		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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 56652 KB Output is correct
2 Correct 53 ms 56764 KB Output is correct
3 Correct 79 ms 56856 KB Output is correct
4 Correct 75 ms 56860 KB Output is correct
5 Correct 78 ms 56860 KB Output is correct
6 Correct 62 ms 56876 KB Output is correct
7 Correct 40 ms 56860 KB Output is correct
8 Correct 43 ms 56788 KB Output is correct
9 Correct 33 ms 56880 KB Output is correct
10 Correct 44 ms 56752 KB Output is correct
11 Correct 41 ms 56884 KB Output is correct
12 Correct 41 ms 56808 KB Output is correct
13 Correct 46 ms 56788 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 56652 KB Output is correct
2 Correct 53 ms 56764 KB Output is correct
3 Correct 79 ms 56856 KB Output is correct
4 Correct 75 ms 56860 KB Output is correct
5 Correct 78 ms 56860 KB Output is correct
6 Correct 62 ms 56876 KB Output is correct
7 Correct 40 ms 56860 KB Output is correct
8 Correct 43 ms 56788 KB Output is correct
9 Correct 33 ms 56880 KB Output is correct
10 Correct 44 ms 56752 KB Output is correct
11 Correct 41 ms 56884 KB Output is correct
12 Correct 41 ms 56808 KB Output is correct
13 Correct 46 ms 56788 KB Output is correct
14 Execution timed out 3095 ms 59392 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 56652 KB Output is correct
2 Correct 53 ms 56764 KB Output is correct
3 Correct 79 ms 56856 KB Output is correct
4 Correct 75 ms 56860 KB Output is correct
5 Correct 78 ms 56860 KB Output is correct
6 Correct 62 ms 56876 KB Output is correct
7 Correct 40 ms 56860 KB Output is correct
8 Correct 43 ms 56788 KB Output is correct
9 Correct 33 ms 56880 KB Output is correct
10 Correct 44 ms 56752 KB Output is correct
11 Correct 41 ms 56884 KB Output is correct
12 Correct 41 ms 56808 KB Output is correct
13 Correct 46 ms 56788 KB Output is correct
14 Execution timed out 3095 ms 59392 KB Time limit exceeded
15 Halted 0 ms 0 KB -