oj.uz

Submission #54613

# Submission time Handle Problem Language Result Execution time Memory
54613 2018-07-04T08:06:25 Z khsoo01 Pairs (IOI07_pairs) C++11
100 / 100
 205 ms 12396 KB 
#include<bits/stdc++.h>
using namespace std;
const int L = 262144;

int n, d, m, x[100005], y[100005], z[100005];

long long ans;

vector<int> a;

void solve1 () {
	for(int i=1;i<=n;i++) {
		scanf("%d",&x[i]);
		a.push_back(x[i]);
	}
	sort(a.begin(), a.end());
	for(int i=0;i<n;i++) {
		int I = lower_bound(a.begin(), a.end(), a[i]-d) - a.begin();
		ans += i - I;
	}
}

struct segtree {
	int v[2*L];
	void upd (int P, int V) {
		P += L;
		while(P) {
			v[P] += V;
			P /= 2;
		}
	}
	int get (int S, int E) {
		S += L;
		E += L;
		int R = 0;
		while(S <= E) {
			if(S % 2 == 1) R += v[S++];
			if(E % 2 == 0) R += v[E--];
			S /= 2;
			E /= 2;
		}
		return R;
	}
} seg;

vector<int> b[150005];

void solve2 () {
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&x[i],&y[i]);
		b[x[i]+y[i]-1].push_back(x[i]-y[i]+m);
	}
	for(int i=1;i<=2*m;i++) {
		for(auto &T : b[i]) {
			ans += seg.get(max(0,T-d), min(2*m,T+d));
			seg.upd(T, 1);
		}
		if(i - d <= 0) continue;
		for(auto &T : b[i-d]) {
			seg.upd(T, -1);
		}
	}
}

int sum[77][155][155];

int f (int Z, int XS, int XE, int YS, int YE) {
	XS = max(XS, 1);
	YS = max(YS, 1);
	XE = min(XE, 2*m);
	YE = min(YE, 2*m);
	return sum[Z][XE][YE] - sum[Z][XS-1][YE] - sum[Z][XE][YS-1] + sum[Z][XS-1][YS-1];
}

void solve3 () {
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d",&x[i],&y[i],&z[i]);
		sum[z[i]][x[i]+y[i]-1][x[i]-y[i]+m]++;
	}
	for(int i=1;i<=m;i++) {
		for(int j=1;j<=2*m;j++) {
			for(int k=1;k<=2*m;k++) {
				sum[i][j][k] += sum[i][j-1][k] + sum[i][j][k-1] - sum[i][j-1][k-1];
			}
		}
	}
	for(int i=1;i<=n;i++) {
		int X = x[i]+y[i]-1, Y = x[i]-y[i]+m, Z = z[i];
		ans += f(Z, X-d, X+d, Y-d, Y+d) - 1;
		for(int j=1;j<=min(d,m);j++) {
			int D = d - j;
			if(Z-j >= 0) ans += f(Z-j, X-D, X+D, Y-D, Y+D);
			if(Z+j <= m) ans += f(Z+j, X-D, X+D, Y-D, Y+D);
		}
	}
	ans /= 2;
}

int main()
{
	int TC;
	scanf("%d%d%d%d",&TC,&n,&d,&m);
	if(TC == 1) solve1();
	if(TC == 2) solve2();
	if(TC == 3) solve3();
	printf("%lld\n",ans);
}

Compilation message

pairs.cpp: In function 'void solve1()':
pairs.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x[i]);
   ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void solve2()':
pairs.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'void solve3()':
pairs.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x[i],&y[i],&z[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&TC,&n,&d,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3832 KB Output is correct
2 Correct 5 ms 4072 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4816 KB Output is correct
2 Correct 25 ms 4824 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4824 KB Output is correct
2 Correct 36 ms 4824 KB Output is correct
3 Correct 33 ms 4852 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5492 KB Output is correct
2 Correct 30 ms 5492 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5568 KB Output is correct
2 Correct 41 ms 5568 KB Output is correct
3 Correct 39 ms 5572 KB Output is correct
4 Correct 43 ms 5604 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8036 KB Output is correct
2 Correct 119 ms 8068 KB Output is correct
3 Correct 51 ms 8068 KB Output is correct
4 Correct 51 ms 8068 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 11108 KB Output is correct
2 Correct 16 ms 11108 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11108 KB Output is correct
2 Correct 40 ms 11108 KB Output is correct
3 Correct 41 ms 11108 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 11108 KB Output is correct
2 Correct 122 ms 11108 KB Output is correct
3 Correct 94 ms 11108 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 12356 KB Output is correct
2 Correct 205 ms 12356 KB Output is correct
3 Correct 126 ms 12396 KB Output is correct