Submission #364859

#	Time	Username	Problem	Language	Result	Execution time	Memory
364859		Bill_00	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	99 ms	27132 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65