제출 #234871

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

fortune_telling2

/*input
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5 +100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
//Trace prints the name of the variable and the value.
int n, k, a[N], b[N];pii ops[N];vector<int> dup;
vector<int> tree[4*N];
void build(int i=1, int l=1, int r=k)
{
	if(l==r) {
		tree[i].push_back(ops[l].s);return;
	}
	int mid=(l+r)>>1;build(2*i, l, mid);build(2*i+1, mid+1, r);
	tree[i].insert(tree[i].end(), tree[2*i].begin(), tree[2*i].end());
	tree[i].insert(tree[i].end(), tree[2*i+1].begin(), tree[2*i+1].end());
	sort(tree[i].begin(), tree[i].end());
}
int ql, qr;
int rmq(int i=1, int l=1, int r=k)
{
	if(l>qr||r<ql) return -inf;
	if(l>=ql&&r<=qr) return tree[i].back();
	int mid=(l+r)>>1;return max(rmq(2*i, l, mid), rmq(2*i+1, mid+1, r));
}	
int val;
int query(int i=1, int l=1, int r=k)
{
	if(l>qr||r<ql) return 0;
	if(l>=ql&&r<=qr)
	{
		auto it=lower_bound(tree[i].begin(), tree[i].end(), val);
		if(it==tree[i].begin()) return tree[i].size();
		if(it==tree[i].end()) return 0;
		int num=(it - tree[i].begin());num=tree[i].size()-num;return num;
	}
	int mid=(l+r)>>1;return query(2*i, l, mid)+ query(2*i+1, mid+1, r);
}
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	for(int i=1;i<=k;i++)
	{
		cin>>ops[i].f;ops[i].s=i;
	}
	sort(ops+1, ops+k+1);
	for(int i=1;i<=k;i++) dup.push_back(ops[i].f);
	build();int ans=0;
	for(int i=1;i<=n;i++)
	{
		
		if(a[i]==b[i]) {ans+=a[i];continue;}
		int mx=max(a[i], b[i]), mn=min(a[i], b[i]);
		auto it=lower_bound(dup.begin(), dup.end(), mn);
		if(it==dup.end())
		{
			ans+=a[i];continue;
		}
		int smn=(it-dup.begin());smn=dup.size() - smn;ql=k-smn + 1;
		
		it=lower_bound(dup.begin(), dup.end(), mx);
		if(it==dup.end())
		{
			ans+=mx;continue;
		}
		qr=(it-dup.begin());
		int lpos;
		if(ql<=qr) lpos=rmq();
		else lpos=inf;
		val=lpos;
		ql=(it-dup.begin())+1;qr=k;int num=query();
		int npos=rmq();
		if(lpos==inf)
		{
			int tm=(qr-ql+1);tm%=2;
			if(tm==0) ans+=a[i];
			else ans+=b[i];continue;
		}
		if(lpos>npos)
		{
			ans+=mx;continue;
		}
		if(lpos<npos)
		{
			if(num%2==0) ans+=mx;
			else ans+=mn;
		}
	}
	cout<<ans<<endl;
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t=1;
	while(t--)
	{
		solve();
	}
}

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

fortune_telling2.cpp: In function 'void solve()':
fortune_telling2.cpp:96:4: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
    else ans+=b[i];continue;
    ^~~~
fortune_telling2.cpp:96:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
    else ans+=b[i];continue;
                   ^~~~~~~~

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