oj.uz

Submission #255884

# Submission time Handle Problem Language Result Execution time Memory
255884 2020-08-02T03:56:02 Z Falcon Pairs (IOI07_pairs) C++14
100 / 100
 801 ms 47736 KB 
#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
	#include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
	#define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
	#define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
	#define debug(x...)
	#define light_debug(x) 
#endif


using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;


void solve1(){
	int N, D, M;
	cin >> N >> D >> M;
	vi A(N);
	rep(i, N)
		cin >> A[i];
	sort(all(A));
	ll ans = -N;
	for(int a : A)
		ans += upper_bound(all(A), a + D) - lower_bound(all(A), a - D);
	cout << (ans >> 1) << '\n';
}

struct Point2D{
	int x, y;
	bool operator<(Point2D& p){
		return x < p.x;
	}
};

template<int... n>
struct BIT{
	int a = 0;

	void upd(int v){
		a += v;
	}

	int qry(){
		return a;
	}
};

template<int n, int... m>
struct BIT<n, m...>{
	BIT<m...> a[n + 1];

	template<typename... args>
	void upd(int i, args... j){
		for(; i <= n; i += i & -i)
			a[i].upd(j...);
	}

	template<typename... args>
	int prf(int i, args... j){
		int s = 0;
		for(; i; i -= i & -i)
			s += a[i].qry(j...);
		return s;
	}

	template<typename... args>
	int qry(int i, int j, args... k){
		return prf(j, k...) - prf(i - 1, k...);
	}
};

void solve2(){
	int N, D, M;
	BIT<150001> bit;
	cin >> N >> D >> M;
	vector<Point2D> A(N);
	rep(i, N){
		int x, y;
		cin >> x >> y;
		A[i] = Point2D{M + x - y, x + y};
	}
	sort(all(A));
	ll ans = -N;
	auto pushx = A.begin(), popx = A.begin(), curx = A.begin();
	for(int x = 1; x <= 2 * M; x++){
		for(; pushx != A.end() && pushx->x <= x + D; pushx++)
			bit.upd(max(1, pushx->y - D), 1), bit.upd(min(pushx->y + D + 1, 2 * M + 1), -1);
		for(; popx != A.end() && popx->x < x - D; popx++)
			bit.upd(max(1, popx->y - D), -1), bit.upd(min(popx->y + D + 1, 2 * M + 1), 1);
		for(; curx != A.end() && curx->x == x; curx++)
			ans += bit.prf(curx->y);
	}
	ans >>= 1;
	cout << ans << '\n';
}

struct Point4D{
	int x, y, z, w;
	bool operator<(Point4D p){
		return x < p.x;
	}
};	


struct BIT3D{ // "cc1plus.exe out of memory" when I tries to use the template
	int a[226][226][226];
	void clip(int& i){
		i = max(1, i);
		i = min(i, 225);
	}

	void upd(int _i, int _j, int _k, int v){
		clip(_i), clip(_j), clip(_k);
		for(int i = _i; i <= 225; i += i & -i)
			for(int j = _j; j <= 225; j += j & -j)
				for(int k = _k; k <= 225; k += k & -k)
					a[i][j][k] += v;
	}

	int qry(int _i, int _j, int _k){
		int s = 0;
		for(int i = _i; i; i -= i & -i)
			for(int j = _j; j; j -= j & -j)
				for(int k = _k; k; k -= k & -k)
					s += a[i][j][k];
		return s;
	}

	void rupd(int i1, int i2, int j1, int j2, int k1, int k2, int v){
		i2++, j2++, k2++;
		upd(i1, j1, k1, v);
		upd(i1, j1, k2, -v);
		upd(i1, j2, k1, -v);
		upd(i1, j2, k2, v);
		upd(i2, j1, k1, -v);
		upd(i2, j1, k2, v);
		upd(i2, j2, k1, v);
		upd(i2, j2, k2, -v);
	}
};

BIT3D bit;
void solve3(){
	
	int N, D, M;
	cin >> N >> D >> M;
	vector<Point4D> A(N);
	rep(i, N){
		int x, y, z;
		cin >> x >> y >> z;
		A[i] = Point4D{x + y + z, M - x + y + z, M + x - y + z, M + x + y - z};
	}
	sort(all(A));

	ll ans = -N;
	auto pushx = A.begin(), popx = A.begin(), curx = A.begin();
	for(int x = 1; x <= 3 * M; x++){
		for(; pushx != A.end() && pushx->x <= x + D; pushx++)
			bit.rupd(pushx->y - D, pushx->y + D, pushx->z - D, pushx->z + D, pushx->w - D, pushx->w + D, 1);
		
		for(; popx != A.end() && popx->x < x - D; popx++)
			bit.rupd(popx->y - D, popx->y + D, popx->z - D, popx->z + D, popx->w - D, popx->w + D, -1);
		for(; curx != A.end() && curx->x == x; curx++)
			ans += bit.qry(curx->y, curx->z, curx->w);
	}

	ans >>= 1;
	cout << ans << '\n';
}

signed main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	#ifdef DEBUG
		freopen("debug", "w", stderr);
	#endif
	
	int B;
	cin >> B;
	if(B == 1) solve1();
	else if(B == 2) solve2();
	else solve3();



	#ifdef DEBUG
		dbg::dout << "\nExecution time: " << clock() << "ms\n";
	#endif

	return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1536 KB Output is correct
2 Correct 25 ms 1664 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1664 KB Output is correct
2 Correct 28 ms 1664 KB Output is correct
3 Correct 29 ms 1664 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2304 KB Output is correct
2 Correct 27 ms 2304 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2432 KB Output is correct
2 Correct 35 ms 2452 KB Output is correct
3 Correct 37 ms 2432 KB Output is correct
4 Correct 31 ms 2432 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2816 KB Output is correct
2 Correct 47 ms 2816 KB Output is correct
3 Correct 41 ms 2816 KB Output is correct
4 Correct 37 ms 2808 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 25728 KB Output is correct
2 Correct 4 ms 1536 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 3712 KB Output is correct
2 Correct 452 ms 4600 KB Output is correct
3 Correct 389 ms 4344 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 24568 KB Output is correct
2 Correct 801 ms 41592 KB Output is correct
3 Correct 207 ms 8056 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 41848 KB Output is correct
2 Correct 782 ms 47736 KB Output is correct
3 Correct 181 ms 10616 KB Output is correct