Submission #340044

#	Time	Username	Problem	Language	Result	Execution time	Memory
340044		erkam	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	27 ms	33900 KiB

fortune_telling2

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#define endl "\n"
#define all(v) v.begin(),v.end()
#define st first
#define nd second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long lo;
const int mod=1000000007,N=500005;
lo a,b,c,d,e,f,g=1,h[N],q;
vector<lo>tree[2*N];
pair<lo,lo> arr[N],degis[N];
string s;
vector<lo>v;


//----------------------------------------segment tree start
void build(lo n,lo l,lo r){
	if(l==r){
		tree[n].pb(degis[n].nd);
		return;
	}
	build(2*n,l,(l+r)/2);
	build(2*n+1,(l+r)/2+1,r);
	lo x=0,y=0;
	for(lo i=0;i<l+r-1;i++){
		if(x==tree[2*n].size())tree[n].pb(tree[2*n+1][y++]);
		else if(y==tree[2*n+1].size())tree[n].pb(tree[2*n][x++]);
		else if(tree[2*n][x]<tree[2*n+1][y])tree[n].pb(tree[2*n][x++]);
		else tree[n].pb(tree[2*n+1][y++]);
	}
}
lo query(lo n,lo l,lo r,lo x,lo y,lo z){
	if(x<=l and r<=y){
		return (tree[n].end()-upper_bound(all(tree[n]),z));
	}
	if(r<x or y<l){
		return 0;
	}
	return query(2*n,l,(l+r)/2,x,y,z)+
		   query(2*n+1,(l+r)/2+1,r,x,y,z);
}
lo query2(lo n,lo l,lo r,lo x,lo y){
	if(x<=l and r<=y){
		return tree[n][tree[n].size()-1];
	}
	if(r<x or y<l){
		return 0;
	}
	return max(query2(2*n,l,(l+r)/2,x,y),query2(2*n+1,(l+r)/2+1,r,x,y));
}
//----------------------------------------segment tree end




lo bs(lo x){
	lo l=1,r=b+1;
	while(l<r){
		lo mid=(l+r)/2;
		if(degis[mid].st<x) l=mid+1;
		else r=mid;
	}
	return r;
}



void solve(){
	cin >> a >> b;
	for(lo i=1;i<=a;i++){
		cin >> arr[i].st >> arr[i].nd;
	}
	for(lo i=1;i<=b;i++){
		cin >> degis[i].st;
		degis[i].nd=i;
	}
	build(1,1,b);
	sort(degis+1,degis+b+1);
	lo sum=0;
	for(lo i=1;i<=a;i++){
		lo x=bs(arr[i].st),y=bs(arr[i].nd);
		if(x<y){
			lo hh=query(1,1,b,y,b,query2(1,1,b,x,y-1));
			sum+=(hh%2?arr[i].st:arr[i].nd);
		}
		if(y<x){
			lo hh=query(1,1,b,x,b,query2(1,1,b,y,x-1));
			sum+=(hh%2?arr[i].nd:arr[i].st);
		}
		if(x==y){
			sum+=((b-y+1)%2?arr[i].nd:arr[i].st);
		}
	}
	cout << sum << endl;
}
 


int main(){
	#ifdef local
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	// cin >> g;
	while(g--)solve();
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void build(lo, lo, lo)':
fortune_telling2.cpp:38:7: warning: comparison of integer expressions of different signedness: 'lo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   if(x==tree[2*n].size())tree[n].pb(tree[2*n+1][y++]);
      |      ~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:39:12: warning: comparison of integer expressions of different signedness: 'lo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   else if(y==tree[2*n+1].size())tree[n].pb(tree[2*n][x++]);
      |           ~^~~~~~~~~~~~~~~~~~~~

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