제출 #398277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398277		keta_tsimakuridze	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	764 ms	35424 KiB

fortune_telling2

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t[N],tree_[N],tree[4*N],a[N],b[N],n,m;
vector<pair<int,int> > q,V;
set<pair<int,int> > s;
void update(int ind){
	for(ind;ind>=1;ind-=ind&(-ind)){
		tree_[ind]++;
	}
}
int getans(int ind){
	int pas=0;
	for(ind;ind<=m;ind+=ind&(-ind)){
		pas+=tree_[ind];
	}
	return pas;
}
void update(int u,int ind,int l,int r,int val){
	if(l>ind || r<ind) return;
	if(l==r) {
		tree[u]=val;
		return;
	}
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val);
	update(2*u+1,ind,mid+1,r,val);
	tree[u]=max(tree[2*u],tree[2*u+1]);
}
int getans(int u,int start,int end,int l,int r){
	if(l>end || r<start) return 0;
	if(start<=l && r<=end) return tree[u];
	int mid=(l+r)/2;
	return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
 main(){
	// t=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];	cin>>b[i];V.push_back({max(b[i],a[i]),i});
	}

	for(int i=1;i<=m;i++){
		cin>>t[i];
		q.push_back({t[i],i});
	}

	sort(V.rbegin(),V.rend());
	sort(q.rbegin(),q.rend());
	for(int i=0;i<q.size();i++){
		s.insert({q[i].f,i+1});
		update(1,i+1,1,m,q[i].s);
	}
	int l = -1,ans=0;
	for(int i=0;i<V.size();i++){
		while(l+1<q.size() && q[l+1].f>=V[i].f) l++,update(q[l].s);
		int lst = 1;
		if(s.upper_bound({min(a[V[i].s],b[V[i].s]),-1})!=s.end() &&(*s.upper_bound({min(a[V[i].s],b[V[i].s]),-1})).s>l+1 ){
			 lst =getans(1,l+2,(*s.upper_bound({min(a[V[i].s],b[V[i].s]),-1})).s,1,m);
			 if(a[V[i].s] < b[V[i].s]) swap(a[V[i].s],b[V[i].s]);
		}
	//cout<<V[i].s<<" "<<lst<<" "<<getans(lst)<<endl;
		if(getans(lst)%2) ans+=b[V[i].s];else ans += a[V[i].s];
	}
	cout<<ans;
	
	
}

컴파일 시 표준 에러 (stderr) 메시지

fortune_telling2.cpp: In function 'void update(long long int)':
fortune_telling2.cpp:11:6: warning: statement has no effect [-Wunused-value]
   11 |  for(ind;ind>=1;ind-=ind&(-ind)){
      |      ^~~
fortune_telling2.cpp: In function 'long long int getans(long long int)':
fortune_telling2.cpp:17:6: warning: statement has no effect [-Wunused-value]
   17 |  for(ind;ind<=m;ind+=ind&(-ind)){
      |      ^~~
fortune_telling2.cpp: At global scope:
fortune_telling2.cpp:39:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 |  main(){
      |       ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:53:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i=0;i<q.size();i++){
      |              ~^~~~~~~~~
fortune_telling2.cpp:58:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0;i<V.size();i++){
      |              ~^~~~~~~~~
fortune_telling2.cpp:59:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   while(l+1<q.size() && q[l+1].f>=V[i].f) l++,update(q[l].s);
      |         ~~~^~~~~~~~~

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