Submission #438819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
438819	2021-06-28T17:05:05 Z	sinamhdv	Pairs (IOI07_pairs)	C++11	47 / 100	4000 ms	304376 KB

pairs

// 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

#	Verdict	Execution time	Memory	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

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

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	4062 ms	12780 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

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

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

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

Submission #438819

Compilation message