Submission #170956

#	Time	Username	Problem	Language	Result	Execution time	Memory
170956		ZwariowanyMarcin	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	541 ms	43864 KiB

fortune_telling2

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;

const int nax = 6e5 + 111;
const int pod = (1 << 20);

int n, k;
int a[nax];
int b[nax];
int q[nax];

vector <int> val;
vector <int> gao[nax];

int pos(int x) {
	return (int) (lower_bound(val.begin(), val.end(), x) - val.begin());
}

struct seg {
	int t[2 * pod];
	
	void init() {
		for(int i = 1; i < 2 * pod; ++i)
			t[i] = 0;
	}
	
	void add(int x, int c) {
		x += pod;
		t[x] = max(t[x], c);
		x /= 2;
		while(x) {
			t[x] = max(t[2 * x], t[2 * x + 1]);
			x /= 2;
		}
	}
	
	int query(int l, int r) {
		r++;
		int res = 0;
		for(l += pod, r += pod; l < r; l /= 2, r /= 2) {
			if(l & 1)
				res = max(res, t[l++]);
			if(r & 1)
				res = max(res, t[--r]);
		}
		return res;
	}
} ja;

struct fen {
	int t[nax];
	
	void init() {
		for(int i = 0; i < nax; ++i)
			t[i] = 0;
	}
	
	void add(int x, int c) {
		for(; x < nax; x += x & -x)
			t[x] += c;
	}
	
	int query(int x) {
		int res = 0;
		for(; 0 < x; x -= x & -x)
			res += t[x];
		return res;
	}
	
	int sum(int l, int r) {
		return query(r) - query(l - 1);
	}
} on;

int main() {
	ja.init();
	on.init();
	val.pb(-1);
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		scanf("%d", b + i);
		val.pb(a[i]);
		val.pb(b[i]);
	}
	for(int i = 1; i <= k; ++i) {
		scanf("%d", q + i);
		val.pb(q[i]);
	}
	sort(val.begin(), val.end());
	val.erase(unique(val.begin(), val.end()), val.end());
	for(int i = 1; i <= n; ++i) {
		a[i] = pos(a[i]);
		b[i] = pos(b[i]);
	}
	for(int i = 1; i <= k; ++i) {
		q[i] = pos(q[i]);
		ja.add(q[i], i);
		gao[q[i]].pb(i);
	}
	ll sum = 0;
	int Last = ss(val);
	vector <int> v;
	for(int i = 1; i <= n; ++i)
		v.pb(i);
	sort(v.begin(), v.end(), [](int x, int y) {
		return max(a[x], b[x]) < max(a[y], b[y]);
	});
	
	for(int i = n - 1; 0 <= i; --i) {
		int ind = v[i];
		for(int j = max(a[ind], b[ind]); j < Last; ++j)
			for(auto it : gao[j])
				on.add(it, 1);
		Last = max(a[ind], b[ind]);
		int wsk = ja.query(min(a[ind], b[ind]), max(a[ind], b[ind]) - 1);
		int hop = on.sum(wsk + 1, k);
		if(wsk > 0) {
			if(hop % 2 == 0)
				sum += val[max(a[ind], b[ind])];
			else
				sum += val[min(a[ind], b[ind])];
		}
		else {
			if(hop % 2 == 0)
				sum += val[a[ind]];
			else
				sum += val[b[ind]];
		}
		
	}
	printf("%lld", sum);
	
	
	
	
	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", b + i);
   ~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", q + i);
   ~~~~~^~~~~~~~~~~~~

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