oj.uz

답안 #656596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656596 2022-11-08T02:14:53 Z mousey 운세 보기 2 (JOI14_fortune_telling2) C++14
4 / 100
 3000 ms 59592 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
#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=40000;
    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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 56608 KB Output is correct
2 Correct 49 ms 56780 KB Output is correct
3 Correct 63 ms 56888 KB Output is correct
4 Correct 61 ms 56864 KB Output is correct
5 Correct 69 ms 56780 KB Output is correct
6 Correct 54 ms 56888 KB Output is correct
7 Correct 37 ms 56848 KB Output is correct
8 Correct 37 ms 56900 KB Output is correct
9 Correct 34 ms 56784 KB Output is correct
10 Correct 45 ms 56800 KB Output is correct
11 Correct 37 ms 56868 KB Output is correct
12 Correct 40 ms 56868 KB Output is correct
13 Correct 39 ms 56788 KB Output is correct

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 56608 KB Output is correct
2 Correct 49 ms 56780 KB Output is correct
3 Correct 63 ms 56888 KB Output is correct
4 Correct 61 ms 56864 KB Output is correct
5 Correct 69 ms 56780 KB Output is correct
6 Correct 54 ms 56888 KB Output is correct
7 Correct 37 ms 56848 KB Output is correct
8 Correct 37 ms 56900 KB Output is correct
9 Correct 34 ms 56784 KB Output is correct
10 Correct 45 ms 56800 KB Output is correct
11 Correct 37 ms 56868 KB Output is correct
12 Correct 40 ms 56868 KB Output is correct
13 Correct 39 ms 56788 KB Output is correct
14 Execution timed out 3056 ms 59592 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 56608 KB Output is correct
2 Correct 49 ms 56780 KB Output is correct
3 Correct 63 ms 56888 KB Output is correct
4 Correct 61 ms 56864 KB Output is correct
5 Correct 69 ms 56780 KB Output is correct
6 Correct 54 ms 56888 KB Output is correct
7 Correct 37 ms 56848 KB Output is correct
8 Correct 37 ms 56900 KB Output is correct
9 Correct 34 ms 56784 KB Output is correct
10 Correct 45 ms 56800 KB Output is correct
11 Correct 37 ms 56868 KB Output is correct
12 Correct 40 ms 56868 KB Output is correct
13 Correct 39 ms 56788 KB Output is correct
14 Execution timed out 3056 ms 59592 KB Time limit exceeded
15 Halted 0 ms 0 KB -