Submission #1277063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277063		Bui_Quoc_Cuong	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	2 ms	576 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
const int LIM = 2e5 + 5;
const int LG = 20;

int n, q;
int a[LIM], b[LIM], dir[LIM], c[LIM], d[LIM];
int st[LIM * LG], L[LIM * LG], R[LIM * LG], node = 0, vers[LIM];

int up(int old, int l, int r, int pos, int val){
	int cur = ++ node;
	if(l == r){
		st[cur] = st[old] + val;
		return cur;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid){
		R[cur] = R[old];
		L[cur] = up(L[old], l, mid, pos, val);
	} else{
		L[cur] = L[old];
		R[cur] = up(R[old], mid + 1, r, pos, val);
	}
	st[cur] = st[L[cur]] + st[R[cur]];
	return cur;
}

int get(int id, int l, int r, int u, int v){
	if(l > v || r < u) return 0;
	if(l >= u && r <= v) return st[id];
	int mid = (l + r) >> 1;
	return get(L[id], l, mid, u, v) + get(R[id], mid + 1, r, u, v);
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    #define kieuoanh "kieuoanh"
    if(fopen(kieuoanh".inp", "r")){
        freopen(kieuoanh".inp", "r", stdin); freopen(kieuoanh".out", "w", stdout);
    }
    cin >> n >> q;
    vector <int> values;
    for(int i = 1; i <= n; i++){
    	cin >> a[i] >> b[i];
    	values.push_back(a[i]);
    	values.push_back(b[i]);
    	c[i] = a[i], d[i] = b[i];
    	if(a[i] > b[i]){
    		swap(a[i], b[i]);
    		dir[i] = 1;
    	}
    }
    vector <int> num_query(q + 2, 0);
    for(int i = 1; i <= q; i++)
    	cin >> num_query[i];
    // tìm query cuối cùng ai <= x < bi
    for(int i = 1; i <= q; i++){
    	values.push_back(num_query[i]);
    }

   	sort(values.begin(), values.end());
   	values.resize(unique(values.begin(), values.end()) - values.begin());

   	for(int i = 1; i <= n; i++){
   		a[i] = upper_bound(values.begin(), values.end(), a[i]) - values.begin();
   		b[i] = upper_bound(values.begin(), values.end(), b[i]) - values.begin();
   	}
   	for(int i = 1; i <= q; i++){
   		num_query[i] = upper_bound(values.begin(), values.end(), num_query[i]) - values.begin();
   	}	
   	int lim = values.size();

   	for(int i = q; i >= 0; i--){
   		vers[i] = vers[i + 1];
   		vers[i] = up(vers[i], 1, lim, num_query[i], 1);
   	}

   	long long ans = 0;

   	for(int i = 1; i <= n; i++){
   		int l = 0, r = q, pos = 0;
   		while(l <= r){
   			int mid = (l + r) >> 1;
   			if(get(vers[mid], 1, lim, a[i], b[i] - 1)) pos = mid, l = mid + 1;
   			else r = mid - 1;
   		}

   		int cnt = (pos != 0) + get(vers[pos], 1, lim, b[i], lim);

   		if((cnt + dir[i]) & 1) ans+= d[i];
   		else ans+= c[i];
   	}
   	
   	cout << ans;

    return 0;
}

Compilation message (stderr)

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

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