oj.uz

Submission #129965

# Submission time Handle Problem Language Result Execution time Memory
129965 2019-07-13T16:32:01 Z tmwilliamlin168 Pairs (IOI07_pairs) C++14
100 / 100
 519 ms 25660 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int b, n, d, m;
long long ans;

namespace subtask2 {
	static const int MG1=1.5e5;
	array<int, 2> a[mxN];
	int ft[MG1];

	void upd(int i, int x) {
		for(++i; i<MG1; i+=i&-i)
			ft[i]+=x;
	}

	int qry(int i) {
		int r=0;
		for(; i; i-=i&-i)
			r+=ft[i];
		return r;
	}

	void solve() {
		for(int i=0; i<n; ++i) {
			cin >> a[i][0];
			if(b^1) {
				cin >> a[i][1];
				tie(a[i][0], a[i][1])=make_pair(a[i][0]+a[i][1], a[i][0]-a[i][1]-1+m);
			}
		}
		sort(a, a+n);
		for(int i=0, j=0; i<n; ++i) {
			while(a[j][0]<a[i][0]-d)
				upd(a[j++][1], -1);
			ans+=qry(min(a[i][1]+d+1, MG1-1))-qry(max(a[i][1]-d, 0));
			upd(a[i][1], 1);
		}
	}
}

namespace subtask3 {
	static const int MG1=223;
	array<int, 3> a[mxN];
	array<int, 4> b[mxN];
	int ft[MG1+1][MG1+1][MG1+1];

	void upd(int i1, int i2, int i3) {
		for(int j1=i1+1; j1<=MG1; j1+=j1&-j1)
			for(int j2=i2+1; j2<=MG1; j2+=j2&-j2)
				for(int j3=i3+1; j3<=MG1; j3+=j3&-j3)
					++ft[j1][j2][j3];
	}

	int qry(int i1, int i2, int i3) {
		int r=0;
		for(int j1=i1; j1; j1-=j1&-j1)
			for(int j2=i2; j2; j2-=j2&-j2)
				for(int j3=i3; j3; j3-=j3&-j3)
					r+=ft[j1][j2][j3];
		return r;
	}

	void solve() {
		for(int i=0; i<n; ++i) {
			cin >> a[i][0] >> a[i][1] >> a[i][2];
			b[i][0]=a[i][0]+a[i][1]+a[i][2]-3;
			b[i][1]=a[i][0]+a[i][1]-a[i][2]-2+m;
			b[i][2]=a[i][0]-a[i][1]+a[i][2]-2+m;
			b[i][3]=a[i][0]-a[i][1]-a[i][2]-1+2*m;
		}
		for(int i=0; i<MG1; ++i) {
			for(int j=0; j<n; ++j)
				if(b[j][3]==i)
					upd(b[j][0], b[j][1], b[j][2]);
			for(int j=0; j<n; ++j) {
				if(i^b[j][3]-d-1&&i^min(b[j][3]+d, MG1-1))
					continue;
				int l1=max(b[j][0]-d, 0), r1=min(b[j][0]+d+1, MG1), l2=max(b[j][1]-d, 0), r2=min(b[j][1]+d+1, MG1), l3=max(b[j][2]-d, 0), r3=min(b[j][2]+d+1, MG1);
				ans+=(i^b[j][3]-d-1?1:-1)*(qry(r1, r2, r3)-qry(r1, r2, l3)-qry(r1, l2, r3)+qry(r1, l2, l3)-qry(l1, r2, r3)+qry(l1, r2, l3)+qry(l1, l2, r3)-qry(l1, l2, l3));
			}
		}
		ans=(ans-n)/2;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> b >> n >> d >> m;
	if(b<3)
		subtask2::solve();
	else
		subtask3::solve();
	cout << ans;
}

Compilation message

pairs.cpp: In function 'void subtask3::solve()':
pairs.cpp:78:19: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     if(i^b[j][3]-d-1&&i^min(b[j][3]+d, MG1-1))
pairs.cpp:81:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     ans+=(i^b[j][3]-d-1?1:-1)*(qry(r1, r2, r3)-qry(r1, r2, l3)-qry(r1, l2, r3)+qry(r1, l2, l3)-qry(l1, r2, r3)+qry(l1, r2, l3)+qry(l1, l2, r3)-qry(l1, l2, l3));

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1284 KB Output is correct
2 Correct 32 ms 1144 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1172 KB Output is correct
2 Correct 37 ms 2044 KB Output is correct
3 Correct 37 ms 2088 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1276 KB Output is correct
2 Correct 36 ms 1304 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1272 KB Output is correct
2 Correct 41 ms 1144 KB Output is correct
3 Correct 41 ms 1144 KB Output is correct
4 Correct 41 ms 1276 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1688 KB Output is correct
2 Correct 44 ms 1660 KB Output is correct
3 Correct 46 ms 2904 KB Output is correct
4 Correct 45 ms 2808 KB Output is correct

Subtask #10
10.0 / 10.0

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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 4092 KB Output is correct
2 Correct 244 ms 4216 KB Output is correct
3 Correct 169 ms 4088 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 18020 KB Output is correct
2 Correct 364 ms 18112 KB Output is correct
3 Correct 203 ms 18000 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 25660 KB Output is correct
2 Correct 426 ms 25528 KB Output is correct
3 Correct 260 ms 25592 KB Output is correct