oj.uz

Submission #841752

# Submission time Handle Problem Language Result Execution time Memory
841752 2023-09-02T03:11:27 Z fanwen Pairs (IOI07_pairs) C++17
60 / 100
 27 ms 3036 KB 
/**
 *      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, 1), 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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 856 KB Output is correct
2 Correct 10 ms 856 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 856 KB Output is correct
2 Correct 14 ms 856 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 856 KB Output is correct
2 Correct 14 ms 860 KB Output is correct
3 Correct 13 ms 860 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 856 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1496 KB Output is correct
2 Correct 18 ms 2012 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1496 KB Output is correct
2 Correct 22 ms 2268 KB Output is correct
3 Correct 22 ms 2268 KB Output is correct
4 Correct 21 ms 2268 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2008 KB Output is correct
2 Correct 26 ms 3036 KB Output is correct
3 Correct 26 ms 3036 KB Output is correct
4 Correct 27 ms 3036 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -