Submission #360187

#	Time	Username	Problem	Language	Result	Execution time	Memory
360187		pure_mem	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	267 ms	12268 KiB

fortune_telling2

#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

const int N = 2e5 + 12;

int n, k, b[N], p[N], f[N];
pair<int, int> a[N];
void upd_f(int v, int val){
	for(;v <= k;v |= v + 1)
		f[v] += val;
}
int get_f(int v){
	int val = 0;
	for(;v >= 0;v = (v & (v + 1)) - 1)
		val += f[v];
	return val;
}
int t[N * 4];
void build(int v, int tl, int tr){
	if(tl == tr){
		t[v] = b[tl];
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm), build(v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void upd(int v, int tl, int tr, int pos, int val){
	if(tl > pos || pos > tr)
		return;
	if(tl == tr){
		t[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, pos, val), upd(v * 2 + 1, tm + 1, tr, pos, val);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int rec(int v, int tl, int tr, int val){
	if(tl == tr)
		return tl;
	int tm = (tl + tr) / 2;
	if(t[v * 2 + 1] >= val)
		return rec(v * 2 + 1, tm + 1, tr, val);
	else if(t[v * 2] >= val)
		return rec(v * 2, tl, tm, val);
	return 0;	
}
int main () {
	scanf("%d %d", &n, &k);
	for(int i = 1;i <= n;i++)
		scanf("%d %d", &a[i].X, &a[i].Y);
	for(int i = 1;i <= k;i++)
		scanf("%d", &b[i]), p[i] = i;
	sort(a + 1, a + n + 1, [](pair<int, int> x, pair<int, int> y){
		return max(x.X, x.Y) > max(y.X, y.Y);
	});
	sort(p + 1, p + k + 1, [](int x, int y){
		return b[x] > b[y];
	});
	build(1, 1, k);
	int ptr = 1;
	ll ans = 0;
	for(int i = 1;i <= n;i++){
		while(ptr <= k && b[p[ptr]] >= max(a[i].X, a[i].Y))
			upd(1, 1, k, p[ptr], 0), upd_f(k - p[ptr] + 1, 1), ptr++;
	    int tmp = rec(1, 1, k, min(a[i].X, a[i].Y));
	    int cnt = get_f(k - tmp);
	    if(tmp != 0){
	    	if(a[i].X < a[i].Y)
	    		swap(a[i].X, a[i].Y);	
	    }
	    if(cnt & 1)
	    	ans += a[i].Y;
	    else
	    	ans += a[i].X;	
	}
	printf("%lld", ans);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   scanf("%d %d", &a[i].X, &a[i].Y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |   scanf("%d", &b[i]), p[i] = i;
      |   ~~~~~^~~~~~~~~~~~~

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