Submission #668658

#	Time	Username	Problem	Language	Result	Execution time	Memory
668658		nolimiya	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	195 ms	11300 KiB

fortune_telling2

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//**gray sety orz**
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<int , int>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 3e5 + 5;
const long long mod = 1e9 + 7 ;
typedef long long ll;
ll l,r,mid;
ll n,m;
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
ll darage[maxm] , ss , mm;
queue<int> q;
bool vis[maxm] , gos[maxm];
pi pedaret[maxm*2];
int rp[maxm*2];
pi w[maxm];
ll dp[maxm];
//ll rw[maxm][maxm];
bool cmp(pi x , pi y){
	return max(x.first,x.second)>max(y.first,y.second);
}
void build(ll v=1 , ll l=1 , ll r=m+1){	
	if(r-l==1){ rp[v] = 0, pedaret[v]={darage[l],l}; return; }
	ll mid = (l+r)/2;
	build(v*2,l,mid) , build(v*2+1,mid,r);
	rp[v]=rp[v*2]+rp[v*2+1];
	pedaret[v]=max(pedaret[v*2],pedaret[v*2+1]);
}
void shift(ll id , ll v=1 , ll l=1 , ll r=m+1){
	if(r-l==1){ rp[v] = 1 , pedaret[v] = {-1 , l}; return; }
	ll mid=(l+r)/2;
	if(id<mid) shift(id , v*2 , l , mid);
	else shift(id , v*2+1 , mid , r);
	rp[v] = rp[v*2] + rp[v*2+1];
	pedaret[v] = max(pedaret[v*2] , pedaret[v*2+1]);
}
ll upd(ll x , ll v=1 , ll l=1 , ll r=m+1){
	if(r-l<=1) return l;
	ll mid = (l+r)/2;
	if(pedaret[v*2+1].first>=x) return upd(x,v*2+1,mid,r);
	else return upd(x,v*2,l,mid);
}
ll get(int lx , int rx , int v=1 , int l=1 , int r=m+1){
	
	if(r<=lx||rx<=l) return 0;
	if(lx<=l&&r<=rx) return rp[v];
	ll mid = (l+r)/2;
	return get(lx,rx,v*2,l,mid)+get(lx,rx,v*2+1,mid,r);
}
map<ll,ll> mp;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >>n>>m;
    for (int i=1; i<=n; i++) cin>>w[i].first>>w[i].second;
    sort(w+1,w+n+1,cmp);
	for (int i=1; i<=m; i++) cin>>darage[i];
	build();
	//cout<<55;
	for (int i=1; i<=n; i++){
		mm = 0;
		if (w[i].second>w[i].first) swap(w[i].first,w[i].second) , mm = 1;
		while (pedaret[1].first>=w[i].first) shift(pedaret[1].second);
		//cout<<<69;
		if (pedaret[1].first>=w[i].second){//cout<<44<<endl;
			//cout<<get(upd(w[i].second),m+1)<<endl;
			if (get(upd(w[i].second),m+1)%2) ss+=w[i].second;
			else ss+=w[i].first;
		}
		//cout<<73;
		else{
			ss+=((mm)?((rp[1]%2)?w[i].first:w[i].second):(((rp[1]%2)?w[i].second:w[i].first)));
		}
		//cout<<i<<endl;
	}
	cout<<ss;
}

Compilation message (stderr)

fortune_telling2.cpp:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      |

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