oj.uz

Submission #317893

# Submission time Handle Problem Language Result Execution time Memory
317893 2020-10-30T17:45:34 Z conthoanco Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 508 ms 18784 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 512 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 16 ms 1660 KB Output is correct
15 Correct 34 ms 2424 KB Output is correct
16 Correct 55 ms 3184 KB Output is correct
17 Correct 77 ms 4600 KB Output is correct
18 Correct 77 ms 4336 KB Output is correct
19 Correct 70 ms 4084 KB Output is correct
20 Correct 77 ms 4464 KB Output is correct
21 Correct 65 ms 4084 KB Output is correct
22 Correct 55 ms 4116 KB Output is correct
23 Correct 53 ms 4212 KB Output is correct
24 Correct 53 ms 4204 KB Output is correct
25 Correct 50 ms 4084 KB Output is correct
26 Correct 61 ms 4080 KB Output is correct
27 Correct 68 ms 4336 KB Output is correct
28 Correct 66 ms 4464 KB Output is correct
29 Correct 67 ms 4336 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 16 ms 1660 KB Output is correct
15 Correct 34 ms 2424 KB Output is correct
16 Correct 55 ms 3184 KB Output is correct
17 Correct 77 ms 4600 KB Output is correct
18 Correct 77 ms 4336 KB Output is correct
19 Correct 70 ms 4084 KB Output is correct
20 Correct 77 ms 4464 KB Output is correct
21 Correct 65 ms 4084 KB Output is correct
22 Correct 55 ms 4116 KB Output is correct
23 Correct 53 ms 4212 KB Output is correct
24 Correct 53 ms 4204 KB Output is correct
25 Correct 50 ms 4084 KB Output is correct
26 Correct 61 ms 4080 KB Output is correct
27 Correct 68 ms 4336 KB Output is correct
28 Correct 66 ms 4464 KB Output is correct
29 Correct 67 ms 4336 KB Output is correct
30 Correct 171 ms 9872 KB Output is correct
31 Correct 274 ms 12520 KB Output is correct
32 Correct 345 ms 14056 KB Output is correct
33 Correct 484 ms 18756 KB Output is correct
34 Correct 151 ms 7784 KB Output is correct
35 Correct 489 ms 18656 KB Output is correct
36 Correct 491 ms 18784 KB Output is correct
37 Correct 491 ms 18684 KB Output is correct
38 Correct 467 ms 17504 KB Output is correct
39 Correct 508 ms 18784 KB Output is correct
40 Correct 386 ms 17248 KB Output is correct
41 Correct 449 ms 17532 KB Output is correct
42 Correct 455 ms 18028 KB Output is correct
43 Correct 285 ms 17120 KB Output is correct
44 Correct 279 ms 17124 KB Output is correct
45 Correct 296 ms 17252 KB Output is correct
46 Correct 331 ms 17248 KB Output is correct
47 Correct 298 ms 18656 KB Output is correct
48 Correct 405 ms 18784 KB Output is correct
49 Correct 390 ms 18656 KB Output is correct