Submission #488323

#	Time	Username	Problem	Language	Result	Execution time	Memory
488323		lukameladze	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	844 ms	47948 KiB

fortune_telling2

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#define pii pair <int, int>
using namespace std;
const int N = 3e5 + 5;
int n,k,a[N],b[N],cnt, x[N],curj,aa,bb,mn,mx,frmt,frm,idd,ans;
vector <pii>v;
vector <pii> v1,v2;
int tree[4*N],tree1[N];
multiset <int> ms;
multiset <int> :: iterator it;
map <int, int > idx;
void upd(int idx, int val) {
	for (int i = idx; i < N; i += i&(-i)) {
		tree1[i] += val;
	}
}
int get1(int idx) {
	int pas = 0;
	for (int i = idx; i > 0 ; i -= i&(-i)) {
		pas += tree1[i];
	}
	return pas;
}
int get(int le, int ri) {
	return get1(ri) - get1(le - 1);
}
void update(int node, int le, int ri, int idx, int val) {
	if (le > idx || ri < idx) {
		return ;
	}
	if (le == ri) {
		tree[node] = max(tree[node],val);
		return ;
	}
	int mid = (le + ri) / 2;
	update(2*node, le, mid,idx,val);
	update(2*node + 1, mid + 1, ri, idx, val);
	tree[node] = max(tree[2*node],tree[2*node + 1]);
}
int getans(int node, int le, int ri, int start, int end) {
	if (le > end || ri < start) return 0;
	if (le >= start && ri <= end) {
		return tree[node];
	}
	int mid = (le + ri) / 2;
	return max(getans(2*node, le, mid, start,end), getans(2*node + 1, mid + 1, ri, start,end));
}
main() {
	cin>>n>>k;
	for (int i = 1; i <= n; i++) {
		cin>>a[i]>>b[i];
		v.pb({max(a[i],b[i]),i});
	}
	for (int i = 1; i <= k; i++) {
		cin>>x[i];
		v1.pb({x[i],i});
		v2.pb({x[i],i});
		ms.insert(x[i]);
	}
	ms.insert(1e9 + 1);
	sort(v.begin(),v.end());reverse(v.begin(),v.end());
	sort(v1.begin(),v1.end()); reverse(v1.begin(), v1.end());
	v2.pb({1e9 + 1, 1});
	sort(v2.begin(),v2.end());
	idx[v2[0].f] = 1;
	cnt = 1;
	for (int i = 1; i < v2.size(); i++) {
		if (v2[i].f != v2[i - 1].f) cnt++;
		idx[v2[i].f] = cnt;
	}
	for (int i = 0; i < (int)v2.size() - 1; i++) {
		update(1,1,k,idx[v2[i].f], v2[i].s);
	}
	curj = 0;
	for (int i = 0; i < v.size(); i++) {
		while(curj < v1.size() && v1[curj].f >= v[i].f) {
			upd(v1[curj].s,1);
			curj++;
		}
		aa = a[v[i].s]; bb = b[v[i].s]; mn = min(aa,bb); mx = max(aa,bb);
		it = ms.lower_bound(mn); frmt = idx[*it];
		it = ms.lower_bound(mx); frm = idx[(*it)] - 1;
		idd = 0;
		if (frmt <= frm) {
			idd = getans(1,1,k,frmt,frm); 
			if (idd != 0) aa = mx, bb = mn;
		}
		if (get(idd + 1, k) % 2 == 1) swap(aa,bb);
		ans += aa; 
	}
	cout<<ans<<"\n";
}

Compilation message (stderr)

fortune_telling2.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main() {
      | ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:71:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 1; i < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~
fortune_telling2.cpp:79:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
fortune_telling2.cpp:80:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   while(curj < v1.size() && v1[curj].f >= v[i].f) {
      |         ~~~~~^~~~~~~~~~~

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