Submission #317893

#	Time	Username	Problem	Language	Result	Execution time	Memory
317893		conthoanco	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	508 ms	18784 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define II pair < int , int > 
#define pb push_back
#define mset(a , b) memset(a , b , sizeof a)
#define all(a) (a).begin() , (a).end()
#define Hmax priority_queue < int > 
#define Hmin priority_queue < int , vector < int > , greater < int > >
#define IImax priority_queue < II > 
#define IImin priority_queue < II , vector < II > , greater < II > >
const int inf = 1e15;
const int N = 2e5 + 5;
int n , k , a[N] , b[N] , c[N] , S[4 * N] , F[N] , Out[N] , Poss[N];
vector < II > List;
vector < int > vc;
void Input()
{
    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];
    	vc.pb(c[i]);
    }
    sort(all(vc));
}
void Update(int Id , int Low , int High , int u , int Val)
{
	if(High < u || Low > u) return;
	if(Low == High)
	{
		S[Id] = max(S[Id] , Val);
		return;
	}

	int Mid = (Low + High) / 2;

	Update(2 * Id , Low , Mid , u , Val);
	Update(2 * Id + 1 , Mid + 1 , High , u , Val);

	S[Id] = max(S[2 * Id] , S[2 * Id + 1]);
}
int Query(int Id , int Low , int High , int u , int v)
{
	if(High < u || Low > v) return 0;
	if(u <= Low && High <= v) return S[Id];

	int Mid = (Low + High) / 2;

	return max(Query(2 * Id , Low , Mid , u , v) , Query(2 * Id + 1 , Mid + 1 , High , u , v));
}
void Up(int Val)
{
	Val = lower_bound(all(vc) , Val) - vc.begin() + 1;
	for(int i = Val ; i >= 1 ; i -= (i & -i))
	{
		F[i]++;
	}
}
int Get(int Val)
{
	Val = lower_bound(all(vc) , Val) - vc.begin() + 1;
	int Ans = 0;
	for(int i = Val ; i <= k ; i += (i & -i))
	{
		Ans += F[i];
	}
	return Ans;
}
void Solve()
{
	for(int i = 1 ; i <= k ; ++i) 
	{
		int Pos = lower_bound(all(vc) , c[i]) - vc.begin() + 1;
		Update(1 , 1 , k , Pos , i);
	}
    for(int i = 1 ; i <= n ; ++i)
    {
    	int Min = min(a[i] , b[i]) , Max = max(a[i] , b[i]);
    	int Low = lower_bound(all(vc) , Min) - vc.begin() + 1;
    	int High = lower_bound(all(vc) , Max) - vc.begin();
    	Poss[i] = Query(1 , 1 , k , Low , High);
    	List.pb({Poss[i] , i});
    }
    sort(List.rbegin() , List.rend());
    int Cur = k;
    for(auto i : List)
    {
    	while(Cur > i.fi)
    	{
    		Up(c[Cur]);
    		Cur--;
    	}
    	Out[i.se] = Get(max(a[i.se] , b[i.se]));
    }
    int Res = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
    	if(Poss[i] == 0)
    	{
    		if(Out[i] % 2 == 1) Res += b[i];
    		else Res += a[i];	
    	}
    	else
    	{
    		if(Out[i] % 2 == 0) Res += max(a[i] , b[i]);
    		else Res += min(a[i] , b[i]);
    	}
    }
    cout << Res;
}
#undef int
int main()
{
    if(fopen("trash.inp" , "r"))
        freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
    // else freopen(".inp" , "r" , stdin) , freopen(".out" , "w" , stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solve();
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  122 |         freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:122:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  122 |         freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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