oj.uz

답안 #669230

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669230 2022-12-06T04:20:21 Z penguin133 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n,m,q;
int ft[200005];
void upd(int p, int v){
	for(;p<=m;p+=(p & -p))ft[p] += v;
}

int query(int p){
	int sum = 0;
	for(;p;p-=(p & -p))sum += ft[p];
	return sum;
}

pi A[200005];
bool cmp(pi a, pi b){
	return max(a.fi, a.se) < max(b.fi, b.se);
}

pi Q[200005];
struct node{
	int s,e,m,val;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = 0;
		if(s != e)l = new node(s, m), r = new node(m+1, e), val = max(l->val, r->val);
		else val = Q[s].se;
	}
	int query(int a, int b){
		if(a == s && b == e)return val;
		else if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return max(l->query(a, m), r->query(m+1, b));
	}
}*root;
void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)cin >> A[i].fi >> A[i].se;
	sort(A+1, A+n+1, cmp);
	for(int i=1;i<=m;i++)cin >> Q[i].fi, Q[i].se = i;
	sort(Q+1, Q+m+1);
	root = new node(1, m);
	int in = 1, cur = 0;
	Q[0].fi = -1e9;
	int ans = 0;
	for(int i=1;i<=n;i++){
		while(in <= m && Q[in].fi < max(A[i].fi, A[i].se))cur = max(cur, Q[in].se), in++;
		int tmp;
		if(Q[in-1].fi < min(A[i].fi, A[i].se)){
			tmp = m - in + 1;
			ans += (tmp%2 ? A[i].se : A[i].fi);
		}
		else {
			int lo = 1, hi = in, ans2 = in + 1;
			while(lo <= hi){
				int mid = (lo + hi)>>1;
				if(Q[mid].fi >= min(A[i].fi, A[i].se))ans2 = mid, hi = mid - 1;
				else lo = mid + 1;
			}
			tmp = m - root->query(ans2, in - 1);
			//cout << tmp << '\n';
			ans += (tmp%2 ? min(A[i].fi, A[i].se) : max(A[i].fi, A[i].se));
		}
		//cout << ans << ' ' << A[i].fi << ' ' << A[i].se << '\n';
	}
	cout << ans;
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

fortune_telling2.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main(){
      | ^~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -