Submission #841751

#	Time	Username	Problem	Language	Result	Execution time	Memory
841751		fanwen	Pairs (IOI07_pairs)	C++17	30 / 100	25 ms	4572 KiB

pairs

/**
 *      author : pham van sam 
 *      created : 02 September 2023 (Saturday)
 **/

#include <bits/stdc++.h>
 
using namespace std;
 
namespace SUB1 {
	void Main() {
		int n, d, m; cin >> n >> d >> m;
		vector <int> a(n);
		for (auto &x : a) cin >> x;
		sort(a.begin(), a.end());
		long long ans = 0;
		for (int i = 1, j = 0; i < n; ++i) {
			while(j < i and a[i] - a[j] > d) j++;
			ans += i - j;
		}
		cout << ans; exit(0);
	}
}

namespace SUB2 {
	template <class T> struct Fenwick_Tree {
		vector<T> bit;
		int n;
		Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
		
		void clear() { fill(bit.begin(), bit.end(), T(0)); }
	
		void update(int u, T val) {
			for (; u <= n; u += u & -u) bit[u] += val;
		}
		
		T get(int u) {
			T ans = 0;
			for (; u; u -= u & -u) ans += bit[u];
			return ans; 
		}
		
		T get(int l, int r) {
			return get(r) - get(l - 1);
		}
	};

	void Main() {
		int n, d, m; cin >> m >> d >> n;
		Fenwick_Tree <int> bit(2 * n);
		vector<pair<int, int>> p;
		for (int i = 0; i < m; ++i) {
			int x, y; cin >> x >> y;
			p.emplace_back(x - y, x + y);
		}
		sort(p.begin(), p.end());
		int j = 0;
		long long ans = 0;
		for (int i = 0; i < m; ++i) {
			while(p[i].first - p[j].first > d) {
				bit.update(p[j++].second, -1);
			}
			ans += bit.get(max(p[i].second - d, 0), min(p[i].second + d, 2 * n));
			bit.update(p[i].second, 1);
		}
		cout << ans;
	}
}

void you_make_it(void) {
    int b; cin >> b;
    if(b == 1) SUB1::Main();
	else if(b == 2) SUB2::Main();
}
 
signed main() {
 
#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();
 
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
 
    you_make_it();
 
    auto end_time = chrono::steady_clock::now();
 
    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
 
    return (0 ^ 0);
}
 
// Dream it. Wish it. Do it.

Compilation message (stderr)

pairs.cpp: In instantiation of 'SUB2::Fenwick_Tree<T>::Fenwick_Tree(int) [with T = int]':
pairs.cpp:50:31:   required from here
pairs.cpp:28:7: warning: 'SUB2::Fenwick_Tree<int>::n' will be initialized after [-Wreorder]
   28 |   int n;
      |       ^
pairs.cpp:27:13: warning:   'std::vector<int> SUB2::Fenwick_Tree<int>::bit' [-Wreorder]
   27 |   vector<T> bit;
      |             ^~~
pairs.cpp:29:3: warning:   when initialized here [-Wreorder]
   29 |   Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
      |   ^~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10