Submission #205690

#	Time	Username	Problem	Language	Result	Execution time	Memory
205690		GioChkhaidze	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1110 ms	50300 KiB

fortune_telling2

#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int Nm=2e5+5;
ll ans;
int n,q,L,R,S;
int l[Nm],r[Nm],t[Nm];
int G[3*Nm],Last[3*Nm],Rf[3*Nm],v[12*Nm];
pair < int , int > Id[Nm];
vector < int > s;
map < int , int > f;

void Build(Tree) {
	if (l==r) { v[h]=Last[l]; return ;}
	Build(Left),Build(Right);
	v[h]=max(v[(h<<1)],v[((h<<1)|1)]);
}

int Get(Tree) {
	if (r<L || R<l) return 0;
	if (L<=l && r<=R) return v[h];
	int x=Get(Left),y=Get(Right);
	return max(x,y);
}

void Up(int x) {
	while (x<=S) {
		G[x]++;
		x+=(x & -x);
	}
}

int Ge(int x) {
	int res=0;
	while (x>0) {
		res+=G[x];
		x-=(x & -x);
	}
	return res;
}

main () {
	scanf("%d%d",&n,&q);
	for (int i=1; i<=n; i++) {
		scanf("%d%d",&l[i],&r[i]);
		s.pb(l[i]),s.pb(r[i]);
	}
	
	for (int i=1; i<=q; i++) {
		scanf("%d",&t[i]);
		s.pb(t[i]);
	}
	
	sort(s.begin(),s.end());
	s.erase(unique(s.begin(),s.end()),s.end());
	
	for (int i=0; i<s.size(); i++) f[s[i]]=i+1,Rf[i+1]=s[i];
	for (int i=1; i<=n; i++) l[i]=f[l[i]],r[i]=f[r[i]];
	for (int i=1; i<=q; i++) t[i]=f[t[i]];
	S=s.size();
	s.clear(),f.clear();
	
	for (int i=1; i<=q; i++) Last[t[i]]=i;
	Build(1,1,S);
	
	for (int i=1; i<=n; i++) {
		L=min(l[i],r[i]),R=max(l[i],r[i])-1;
		Id[i].F=Get(1,1,S),Id[i].S=i;
	}
	
	sort(Id+1,Id+n+1);
	
	int Q=q,tot=0;
	for (int i=n; i>=1; i--) {
		while (Q && Id[i].F<Q) Up(t[Q]),--Q;
		tot=Ge(S)-Ge(max(l[Id[i].S],r[Id[i].S])-1);
		
		if (Id[i].F && l[Id[i].S]<r[Id[i].S]) 
			swap(l[Id[i].S],r[Id[i].S]);

		if (tot%2) 
			ans+=Rf[r[Id[i].S]];
				else 
			ans+=Rf[l[Id[i].S]];
	}	
	
	printf("%lld\n",ans);
}

Compilation message (stderr)

fortune_telling2.cpp:48:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<s.size(); i++) f[s[i]]=i+1,Rf[i+1]=s[i];
                ~^~~~~~~~~
fortune_telling2.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t[i]);
   ~~~~~^~~~~~~~~~~~

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