Submission #751599

#	Time	Username	Problem	Language	Result	Execution time	Memory
751599		aebov	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	9 ms	14548 KiB

fortune_telling2

#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
//#pragma GCC optimize("fast-math")
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<utility>
#include<algorithm>
#include<bitset>
#include<map>
#include<iomanip>
#include<set>
#include<string.h>
#include<stack>
#include <list>
#include <numeric>
#include <random>
#include<unordered_map>
#define all(x) x.begin(), x.end()
#define ln (e-s+1)
#define lc (id<<1)
#define rc ((id<<1) | 1)
#define md ((e+s)>>1)
#define dm (((e+s)>>1)+1)
#define pb push_back
#define ll long long 
#define endl '\n'
#define mk make_pair
#define F first
#define pll pair<ll, ll>
#define S second
#define pvv pair<vector<int> , vector<int> > 
#define pii pair<int,int>
#define plll pair<ll, pair<int, int> >
#define ld long double
#define mat vector<vector<ll>>
//#define int long long 
using namespace std;
 
const int N = (int)2e5 + 2, mod = (int) 1e9 + 7;
int n, k, a[N], b[N], sum[N * 3], qer[N], nsa[N], ansi[N], t[N], mn, mx;
vector<int> seg[N * 3];
vector<pii> vec, cev;
bool bl[N];

void build(int id = 1,int s = 1,int e = k){
	if(ln == 1){
		seg[id].pb(t[s]);
		return;
	}build(lc, s, md), build(rc, dm, e);
	for(int x : seg[lc]) seg[id].pb(x);
	for(int x : seg[rc]) seg[id].pb(x);
	sort(seg[id].begin(), seg[id].end());
}
int get(int l2,int r2,int id = 1,int s = 1,int e = k){
	if( l2 <= s && e <= r2){
		int l = 0, r = seg[id].size() - 1, ans = -1;
		while(l <= r){
			int mid = (l+r) >> 1;
			if(seg[id][mid] >= mn) ans = mid, r = mid - 1;
			else l = mid + 1;
		}
		if(ans == -1) return mod;
		return seg[id][ans];
	}
	int g1 = mod, g2 = mod;
	if(!(l2 > md || r2 < s))g1 = get(l2, r2, lc, s, md);
	if(!(l2 > e || r2 < dm))g2 = get(l2, r2, rc, dm, e);
	return min(g1, g2);
}
void updsm(int p,int id = 1,int s = 1,int e = k){
	if(ln == 1){
		sum[id] ++;
		return;
	}
	if(p <= md) updsm(p, lc, s, md);
	else updsm(p, rc, dm, e);
	sum[id] = sum[lc] + sum[rc];
}
int getsm(int l,int r,int id = 1,int s = 1,int e = k){
	if(l > e || r < s) return 0;
	if(l <= s && e <= r) return sum[id];
	int g1 = 0, g2 = 0;
	if(!(l > md || r < s))g1 = getsm(l, r, lc, s, md);
	if(!(l > e || r < dm))g2 = getsm(l, r, rc, dm, e);
	return g1 + g2;
}
int main(){
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i ++) 
		scanf("%d%d", &a[i],&b[i]), vec.pb({max(a[i], b[i]), i}),cev.pb({min(a[i], b[i]), i});
	for(int i = 1; i <= k; i ++) scanf("%d", &t[i]), vec.pb({t[i], i + n}), cev.pb({t[i], i + n});
	sort(cev.begin(), cev.end());
	reverse(cev.begin(), cev.end());
	build();
	ll ret = 0;
	set<pii> st;
 	for(auto [x, y] : cev){
		if(y > n) st.insert({-x,-(y-n)});
		else ansi[y] = -((*st.upper_bound({-max(a[y],b[y]),-mod})).S);
	}
	for(int i = 1; i <= n; i ++){
		qer[i] = ansi[i];
		if(get(1, ansi[i] - 1) < mx)bl[i] = 1;
	}
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	for(auto [x, y] : vec){
		if(y > n) updsm(y-n);//,cout << endl;
		else nsa[y] = getsm(qer[y] , k);//,cout << " few " << " , " << qer[y] << " " <<getsm(qer[y], k) << endl;
	}
	for(int i = 1; i <= n; i ++){
		if(bl[i]){
			if(nsa[i]%2) ret += min(a[i], b[i]);
			else ret += max(a[i], b[i]);
		}else{
			if(nsa[i]%2) ret += b[i];
			else ret += a[i];
		}
	}
	
	cout << ret << endl;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%d%d", &a[i],&b[i]), vec.pb({max(a[i], b[i]), i}),cev.pb({min(a[i], b[i]), i});
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:95:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  for(int i = 1; i <= k; i ++) scanf("%d", &t[i]), vec.pb({t[i], i + n}), cev.pb({t[i], i + n});
      |                               ~~~~~^~~~~~~~~~~~~

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