Submission #317581

#	Time	Username	Problem	Language	Result	Execution time	Memory
317581		hoangtung_pro	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	467 ms	9812 KiB

fortune_telling2

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define bit(s, i) (s & (1<<i))

using namespace std;

const int N = 2e5 + 5;
const int M = 1;
const int K = 1;
const int mod = 1e9+7;
const int inf = 2e9;
const long long Inf = 2e18;

typedef long long ll;
typedef pair < int, int > ii;

int n, k, a[N], b[N], c[N], poss[N], final[N];
vector < int > val;
vector < ii > reqry;
/// IT

int IT[4 * N];
void update(int id, int l, int r, int pos, int x) {
	if(l > pos || r < pos) return;

	if(l == r) {
		IT[id] = max(IT[id], x);
		return;
	}

	int mid = (l + r) >> 1;
	update(id<<1, l, mid, pos, x);
	update(id<<1|1, mid + 1, r, pos, x);

	IT[id] = max(IT[id<<1], IT[id<<1|1]);
}

int query(int id, int l, int r, int u, int v) {
	if(l > v || r <  u) return 0;
	
	if(u <= l && r <= v) return IT[id];

	int mid = (l + r) >> 1;

	return max(query(id<<1, l, mid, u, v), query(id<<1|1, mid + 1, r, u, v)); 
}

/// BIT 
int BIT[N];

void up(int id) {
	id = lower_bound(val.begin(), val.end(), id) - val.begin() + 1;
	for(; id; id -= id&-id) BIT[id] ++;
}

int get(int id) {
	id = lower_bound(val.begin(), val.end(), id) - val.begin() + 1;
	int tmp = 0;
	for(; id <= k; id += id&-id) tmp += BIT[id];
	return tmp;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen("trash.inp", "r")) {    
	    freopen("trash.inp","r",stdin);
	    freopen("trash.out","w",stdout);
    }
    cin >> n >> k;
    for(int i=1;i<=n;++i) cin >> a[i] >> b[i];
    for(int i=1;i<=k;++i) {
    	cin >> c[i];
    	val.pb(c[i]);
	}
	sort(val.begin(), val.end());

	for(int i=1;i<=k;++i) {
		int cur = lower_bound(val.begin(), val.end(), c[i]) - val.begin() + 1;
		update(1, 1, k, cur, i);
	}

	for(int i=1;i<=n;++i) {
		int mi = min(a[i], b[i]);
		int ma = max(a[i], b[i]);
		int L = lower_bound(val.begin(), val.end(), mi) - val.begin() + 1;
		int R = lower_bound(val.begin(), val.end(), ma) - val.begin();

		int cur = query(1, 1, k, L, R);
		poss[i] = cur;
		reqry.pb({cur, i});
	}

	sort(reqry.begin(), reqry.end());
	int run = 1;

	for(ii i : reqry) { 
		while(run <= i.fi) up(c[run ++ ]);
		int ma = max(a[i.se], b[i.se]);
		int ans = get(ma);
		int res = k - (lower_bound(val.begin(), val.end(), ma) - val.begin());
		final[i.se] = res - ans;
		// cout << i.se << ' ' << res << ' ' << ans << endl;
	}

	ll kqua = 0;

	for(int i=1;i<=n;++i) {
		if(!poss[i]) {
			if(final[i]&1) kqua += b[i];
			else kqua += a[i];
		}
		else {
			int cur = (a[i] < b[i]) ^ (final[i]&1);
			if(cur) kqua += b[i];
			else kqua += a[i];
		}
	}
	cout << kqua;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:71:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   71 |      freopen("trash.inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:72:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   72 |      freopen("trash.out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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