Submission #54613

#	Time	Username	Problem	Language	Result	Execution time	Memory
54613		khsoo01	Pairs (IOI07_pairs)	C++11	100 / 100	205 ms	12396 KiB

pairs

#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 (stderr)

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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10