oj.uz

답안 #438819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
438819 2021-06-28T17:05:05 Z sinamhdv Pairs (IOI07_pairs) C++11
47 / 100
 4000 ms 304376 KB 
// IOI07_pairs
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (int)(b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 100100
#define MAXA 75100
const int bs = 80;

int B, n, d, m;
ll ans;
pii pnt[MAXN];
vector<int> seg[4 * MAXN];
int ps[80][220][220];

void build(int v = 1, int l = 0, int r = n - 1)
{

}

int get(int L, int R, int ly, int ry, int v = 1, int l = 0, int r = n - 1)
{
	int res = 0;
	FOR(i, L, R + 1) if (pnt[i].sc <= ry && pnt[i].sc >= ly) res++;
	return res;
}

int32_t main(void)
{
	fast_io;
	cin >> B >> n >> d >> m;
	if (B == 1)
	{
		vector<int> vec(m + 10);
		int x[MAXN] = {};
		FOR(i, 0, n)
		{
			cin >> x[i];
			vec[x[i]]++;
		}
		FOR(i, 1, (int)vec.size()) vec[i] += vec[i - 1];
		FOR(i, 0, n) ans += vec[min(x[i] + d, m+3)] - vec[max(x[i] - d - 1, 0)];
		ans -= n;
		ans /= 2;
		cout << ans << endl;
		return 0;
	}
	else if (B == 3)
	{
		int x[MAXN], y[MAXN], z[MAXN];
		FOR(i, 0, n)
		{
			int a, b, c;
			cin >> a >> b >> c;
			x[i] = a;
			y[i] = b + c;
			z[i] = b - c;
			ps[x[i]][y[i]+bs][z[i]+bs]++;
		}

		FOR(i, 0, 80)
		{
			FOR(j, 1, 220) FOR(k, 1, 220) ps[i][j][k] += ps[i][j - 1][k] + ps[i][j][k - 1] - ps[i][j - 1][k - 1];
		}
		
		FOR(i, 0, n)
		{
			int up = max(x[i] - d, 0);
			int dn = min(x[i] + d, m);
			dbg(i);
			dbg(up);
			dbg(dn);
			FOR(l, up, dn + 1)
			{
				int dis = abs(x[i] - l);
				d -= dis;
				int y1 = max(-77, y[i] - d) - 1 + bs;
				int y2 = min(155, y[i] + d) + bs;
				int z1 = max(-77, z[i] - d) - 1 + bs;
				int z2 = min(155, z[i] + d) + bs;
				ans += ps[l][y2][z2] - ps[l][y1][z2] - ps[l][y2][z1] + ps[l][y1][z1];
				d += dis;
			}
		}

		ans -= n;
		ans /= 2;
		cout << ans << endl;
		return 0;
	}

	// B == 2
	FOR(i, 0, n)
	{
		int x, y;
		cin >> x >> y;
		pnt[i].fr = x + y;
		pnt[i].sc = x - y;
	}
	sort(pnt, pnt + n);
	build();

//	FOR(i, 0, n)
//		cout << "( " << pnt[i].fr << ", " << pnt[i].sc << ") ";
//	cout << endl;

	FOR(i, 0, n)
	{
		int lx = pnt[i].fr - d;
		int rx = pnt[i].fr + d;
		int ly = pnt[i].sc - d;
		int ry = pnt[i].sc + d;
		int L = lower_bound(pnt, pnt + n, mp(lx, 0)) - pnt;
		int R = lower_bound(pnt, pnt + n, mp(rx + 1, 0)) - pnt - 1;
		ans += get(L, R, ly, ry);
	}

	ans -= n;
	ans /= 2;
	cout << ans << endl;

	return 0;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10828 KB Output is correct
2 Correct 8 ms 10896 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 350 ms 304376 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 11212 KB Output is correct
2 Correct 16 ms 11164 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 285720 KB Output is correct
2 Correct 349 ms 285656 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 380 ms 285724 KB Output is correct
2 Correct 336 ms 285676 KB Output is correct
3 Correct 339 ms 285792 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 10912 KB Output is correct
2 Correct 10 ms 10828 KB Output is correct

Subtask #7
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 722 ms 12232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1542 ms 12428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4062 ms 12780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 25932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 26564 KB Output is correct
2 Correct 60 ms 26648 KB Output is correct
3 Correct 65 ms 26564 KB Output is correct

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 26860 KB Output is correct
2 Incorrect 602 ms 26868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 402 ms 26876 KB Output isn't correct
2 Halted 0 ms 0 KB -