oj.uz

Submission #317574

# Submission time Handle Problem Language Result Execution time Memory
317574 2020-10-30T02:41:15 Z hoangtung_pro Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 1 ms 384 KB 
#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define bit(s, i) (s & (1<<i))

using namespace std;

const int N = 2e5 + 5;
const int M = 1;
const int K = 1;
const int mod = 1e9+7;
const int inf = 2e9;
const long long Inf = 2e18;

typedef long long ll;
typedef pair < int, int > ii;

int n, k, a[N], b[N], c[N], poss[N], final[N];
vector < int > val;
vector < ii > reqry;
/// IT

int IT[4 * N];
void update(int id, int l, int r, int pos, int x) {
	if(l > pos || r < pos) return;

	if(l == r) {
		IT[id] = max(IT[id], x);
		return;
	}

	int mid = (l + r) >> 1;
	update(id<<1, l, mid, pos, x);
	update(id<<1|1, mid + 1, r, pos, x);

	IT[id] = max(IT[id<<1], IT[id<<1|1]);
}

int query(int id, int l, int r, int u, int v) {
	if(l > v || r <  u) return 0;
	
	if(u <= l && r <= v) return IT[id];

	int mid = (l + r) >> 1;

	return max(query(id<<1, l, mid, u, v), query(id<<1|1, mid + 1, r, u, v)); 
}

/// BIT 
int BIT[N];

void up(int id) {
	id = lower_bound(val.begin(), val.end(), id) - val.begin() + 1;
	for(; id; id -= id&-id) BIT[id] ++;
}

int get(int id) {
	id = lower_bound(val.begin(), val.end(), id) - val.begin() + 1;
	int tmp = 0;
	for(; id <= k; id += id&-id) tmp += BIT[id];
	return tmp;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("trash.inp","r",stdin);
    // freopen("trash.out","w",stdout);

    cin >> n >> k;
    for(int i=1;i<=n;++i) cin >> a[i] >> b[i];
    for(int i=1;i<=k;++i) {
    	cin >> c[i];
    	val.pb(c[i]);
	}
	val.erase(unique(val.begin(), val.end()), val.end());

	for(int i=1;i<=k;++i) {
		int cur = lower_bound(val.begin(), val.end(), c[i]) - val.begin() + 1;
		update(1, 1, k, cur, i);
	}

	for(int i=1;i<=n;++i) {
		int mi = min(a[i], b[i]);
		int ma = max(a[i], b[i]);
		int L = lower_bound(val.begin(), val.end(), mi) - val.begin() + 1;
		int R = lower_bound(val.begin(), val.end(), ma) - val.begin();

		int cur = query(1, 1, k, L, R);
		poss[i] = cur;
		reqry.pb({cur, i});
	}

	sort(reqry.begin(), reqry.end());
	int run = 1;

	for(ii i : reqry) { 
		while(run <= i.fi) up(c[run ++ ]);
		int ma = max(a[i.se], b[i.se]);
		int ans = get(ma);
		int res = k - (lower_bound(val.begin(), val.end(), ma) - val.begin());
		final[i.se] = res - ans;
	}

	ll kqua = 0;

	for(int i=1;i<=n;++i) {
		if(!poss[i]) {
			if(final[i]&1) kqua += a[i];
			else kqua += b[i];
		}
		else {
			int cur = (a[i] < b[i]) ^ (final[i]&1);
			if(cur) kqua += a[i];
			else kqua += b[i];
		}
	}
	cout << kqua;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -