oj.uz

Submission #364859

# Submission time Handle Problem Language Result Execution time Memory
364859 2021-02-10T09:56:55 Z Bill_00 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 99 ms 27132 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define N 200001
typedef long long ll;
const long long MOD=1000000007;
using namespace std;
int n,k;
int a[N],b[N],mx[4*N+4];
pair<int,int>t[N];
vector<int>v[4*N+4];
void build(int id,int l,int r){
	if(l==r){
		v[id].pb(t[l].ss);
		mx[id]=t[l].ss;
		return;
	}
	int m=l+r>>1;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	mx[id]=max(mx[id*2],mx[id*2+1]);
	int i=0,j=0;
	while(i<v[id*2].size() && j<v[id*2+1].size()){
		if(v[id*2][i]<v[id*2+1][j]){
			v[id].pb(v[id*2][i]);
			i++;
		}
		else{
			v[id].pb(v[id*2+1][j]);
			j++;
		}
	}
	while(i<v[id*2].size()){
		v[id].pb(v[id*2][i]);
		i++;
	}
	while(j<v[id*2+1].size()){
		v[id].pb(v[id*2+1][j]);
		j++;
	}
}
int query1(int id,int l,int r,int L,int R){
	if(r<L || R<l) return 0;
	if(L<=l && r<=R) return mx[id];
	int m=l+r>>1;
	return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R));
}
int query2(int id,int l,int r,int L,int R,int k){

		// cout << v[id].size() << ' ' << l << ' ' << r << '\n';
	if(r<L || R<l) return 0;
	if(L<=l && r<=R){
		return v[id].size()-(lower_bound(v[id].begin(),v[id].end(),k)-v[id].begin());
	}

	int m=l+r>>1;
	return (query2(id*2,l,m,L,R,k)+query2(id*2+1,m+1,r,L,R,k));
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i=1;i<=n;i++){
		cin >> a[i] >> b[i];
	}
	for(int i=1;i<=k;i++){
		cin >> t[i].ff;
		t[i].ss=i;
	}
	int y=0;
	/*for(int i=1;i<=n;i++){
		pair<int,int>l={a[i],b[i]};
		for(int j=1;j<=k;j++){
			if(t[j].ff>=l.ff) swap(l.ff,l.ss);
		}
		cout << l.ff << ' ';
	}
	cout << '\n';*/
	sort(t+1,t+k+1);
	build(1,1,k);
	ll ans=0;
	for(int i=1;i<=n;i++){
		pair<int,int>temp={min(a[i],b[i]),0};
		int l=(lower_bound(t+1,t+k+1,temp)-(t+1));
		l++;
		temp={max(a[i],b[i]),0};
		int r=(lower_bound(t+1,t+k+1,temp)-(t+1));
		if(l>r){
			ans+=(ll)(((n-r)%2)?b[i]:a[i]);
		}
		else{
			int p=query1(1,1,k,l,r);
			int u=query2(1,1,k,r+1,k,p);
			// cout << r << " SKKSK" << ' ';
			ans+=(ll)((u%2)?min(a[i],b[i]):max(a[i],b[i]));
		}
	}
	cout << ans;

}

Compilation message

fortune_telling2.cpp: In function 'void build(int, int, int)':
fortune_telling2.cpp:19:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |  int m=l+r>>1;
      |        ~^~
fortune_telling2.cpp:24:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  while(i<v[id*2].size() && j<v[id*2+1].size()){
      |        ~^~~~~~~~~~~~~~~
fortune_telling2.cpp:24:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  while(i<v[id*2].size() && j<v[id*2+1].size()){
      |                            ~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:34:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  while(i<v[id*2].size()){
      |        ~^~~~~~~~~~~~~~~
fortune_telling2.cpp:38:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  while(j<v[id*2+1].size()){
      |        ~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int query1(int, int, int, int, int)':
fortune_telling2.cpp:46:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int m=l+r>>1;
      |        ~^~
fortune_telling2.cpp: In function 'int query2(int, int, int, int, int, int)':
fortune_telling2.cpp:57:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  int m=l+r>>1;
      |        ~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:72:6: warning: unused variable 'y' [-Wunused-variable]
   72 |  int y=0;
      |      ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19308 KB Output is correct
2 Correct 14 ms 19308 KB Output is correct
3 Correct 14 ms 19308 KB Output is correct
4 Correct 15 ms 19308 KB Output is correct
5 Correct 15 ms 19308 KB Output is correct
6 Correct 15 ms 19308 KB Output is correct
7 Correct 14 ms 19328 KB Output is correct
8 Correct 14 ms 19308 KB Output is correct
9 Correct 14 ms 19308 KB Output is correct
10 Correct 14 ms 19308 KB Output is correct
11 Correct 15 ms 19308 KB Output is correct
12 Correct 14 ms 19308 KB Output is correct
13 Correct 14 ms 19308 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19308 KB Output is correct
2 Correct 14 ms 19308 KB Output is correct
3 Correct 14 ms 19308 KB Output is correct
4 Correct 15 ms 19308 KB Output is correct
5 Correct 15 ms 19308 KB Output is correct
6 Correct 15 ms 19308 KB Output is correct
7 Correct 14 ms 19328 KB Output is correct
8 Correct 14 ms 19308 KB Output is correct
9 Correct 14 ms 19308 KB Output is correct
10 Correct 14 ms 19308 KB Output is correct
11 Correct 15 ms 19308 KB Output is correct
12 Correct 14 ms 19308 KB Output is correct
13 Correct 14 ms 19308 KB Output is correct
14 Correct 30 ms 21100 KB Output is correct
15 Correct 50 ms 23148 KB Output is correct
16 Correct 70 ms 24300 KB Output is correct
17 Correct 95 ms 27116 KB Output is correct
18 Correct 99 ms 27132 KB Output is correct
19 Correct 94 ms 27116 KB Output is correct
20 Correct 95 ms 27116 KB Output is correct
21 Correct 86 ms 27116 KB Output is correct
22 Correct 78 ms 26604 KB Output is correct
23 Correct 71 ms 26604 KB Output is correct
24 Correct 72 ms 26604 KB Output is correct
25 Correct 70 ms 26732 KB Output is correct
26 Incorrect 83 ms 27116 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19308 KB Output is correct
2 Correct 14 ms 19308 KB Output is correct
3 Correct 14 ms 19308 KB Output is correct
4 Correct 15 ms 19308 KB Output is correct
5 Correct 15 ms 19308 KB Output is correct
6 Correct 15 ms 19308 KB Output is correct
7 Correct 14 ms 19328 KB Output is correct
8 Correct 14 ms 19308 KB Output is correct
9 Correct 14 ms 19308 KB Output is correct
10 Correct 14 ms 19308 KB Output is correct
11 Correct 15 ms 19308 KB Output is correct
12 Correct 14 ms 19308 KB Output is correct
13 Correct 14 ms 19308 KB Output is correct
14 Correct 30 ms 21100 KB Output is correct
15 Correct 50 ms 23148 KB Output is correct
16 Correct 70 ms 24300 KB Output is correct
17 Correct 95 ms 27116 KB Output is correct
18 Correct 99 ms 27132 KB Output is correct
19 Correct 94 ms 27116 KB Output is correct
20 Correct 95 ms 27116 KB Output is correct
21 Correct 86 ms 27116 KB Output is correct
22 Correct 78 ms 26604 KB Output is correct
23 Correct 71 ms 26604 KB Output is correct
24 Correct 72 ms 26604 KB Output is correct
25 Correct 70 ms 26732 KB Output is correct
26 Incorrect 83 ms 27116 KB Output isn't correct
27 Halted 0 ms 0 KB -