Submission #94930

#	Time	Username	Problem	Language	Result	Execution time	Memory
94930		Retro3014	Pairs (IOI07_pairs)	C++17	70 / 100	224 ms	12592 KiB

pairs

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <deque>

using namespace std;
#define MAX_M2 75000
#define MAX_M 300000000
#define MAX_D 100000000
typedef long long ll;
int B, N, D, M;


void solve1(){
	ll ans = 0;
	vector<int> v(N);
	deque<int> dq(0);
	for(int i=0; i<N; i++){
		scanf("%d", &v[i]);
	}
	sort(v.begin(), v.end());
	for(int i=0; i<v.size(); i++){
		while(!dq.empty() && dq.front()<v[i]-D){
			dq.pop_front();
		}
		ans+=dq.size();
		dq.push_back(v[i]);
	}
	printf("%lld", ans);
	return;
}

struct SEG{
	int l=-1, r=-1;
	int cnt = 0;
};
vector<SEG> seg;
SEG ss;

struct P{
	int x, y;
	int p;
	bool operator <(const P &a)const{
		if(x==a.x){
			return p>a.p;
		}
		return x<a.x;
	}
};

vector<P> q;

void update(int x, int s, int e, int y){
	if(y<0)	return;
	seg[x].cnt++;
	if(s==e)	return;
	int mid = (s+e)/2;
	if(y<=mid){
		if(seg[x].l==-1){
			seg[x].l=seg.size();
			seg.push_back(ss);
		}update(seg[x].l, s, mid, y);
	}else{
		if(seg[x].r==-1){
			seg[x].r = seg.size();
			seg.push_back(ss);
		}update(seg[x].r, mid+1, e, y);
	}
}

int sum(int x, int s, int e, int y){
	if(y<0)	return 0;
	if(x==-1)	return 0;
	if(e<=y){
		return seg[x].cnt;
	}
	if(s>y)	return 0;
	int mid = (s+e)/2;
	return sum(seg[x].l, s, mid, y) + sum(seg[x].r, mid+1, e, y);
}

void solve2(){
	seg.push_back(ss);
	ll ans = 0;
	vector<P> v(N);
	for(int i=0; i<N; i++){
		scanf("%d%d", &v[i].x, &v[i].y);
	}
	for(int i=0; i<N; i++){
		q.push_back({v[i].x+v[i].y+MAX_D, v[i].x-v[i].y+MAX_M2+MAX_D, 2});
		q.push_back({v[i].x+v[i].y+D+MAX_D, v[i].x-v[i].y+D+MAX_M2+MAX_D, 1});
		q.push_back({v[i].x+v[i].y+D+MAX_D, v[i].x-v[i].y-D-1+MAX_M2+MAX_D, 0});
		q.push_back({v[i].x+v[i].y-D-1+MAX_D, v[i].x-v[i].y+D+MAX_M2+MAX_D, 0});
		q.push_back({v[i].x+v[i].y-D-1+MAX_D, v[i].x-v[i].y-D-1+MAX_M2+MAX_D, 1});
	}
	sort(q.begin(), q.end());
	for(int i=0; i<q.size(); i++){
		if(q[i].p==2){
			update(0, 0, MAX_M, q[i].y);
		}else if(q[i].p==1){
			ans+=sum(0, 0, MAX_M, q[i].y);
		}else{
			ans-=sum(0, 0, MAX_M, q[i].y);
		}
	}
	ans-=N;
	ans/=2;
	printf("%lld", ans);
	return;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct S{
	int x, y, z;
};
#define MAX_M3 75

int sum2[MAX_M3+1][MAX_M3*2+1][MAX_M3*2+1];

ll s(int x, int y, int z){
	if(x<0 || y<0 || z<0)	return 0;
	return (ll)sum2[min(MAX_M3, x)][min(MAX_M3*2, y)][min(MAX_M3*2, z)];
}

void solve3(){
	vector<S> v(N);
	ll ans = 0;
	for(int i=0; i<N; i++)	scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].z);
	for(int i=0; i<N; i++)	sum2[v[i].x][v[i].y+v[i].z][v[i].y-v[i].z+MAX_M3]++;
	for(int i=0; i<=MAX_M3; i++){
		for(int j=0; j<MAX_M3*2; j++){
			for(int k=0; k<MAX_M3*2; k++){
				if(j==0){
					if(k!=0)	sum2[i][j][k]+=sum2[i][j][k-1];
				}else{
					if(k==0)	sum2[i][j][k]+=sum2[i][j-1][k];
					else	sum2[i][j][k]+=sum2[i][j-1][k]+sum2[i][j][k-1]-sum2[i][j-1][k-1];
				}
			}
		}
	}
	for(int i=0; i<N; i++){
		int t = D;
		int a = v[i].y+v[i].z, b = v[i].y-v[i].z+MAX_M3;
		for(int x=v[i].x; x>=1; x--){
			if(t<0)	break;
			ans += s(x, a+t, b+t) - s(x, a+t, b-t-1) - s(x, a-t-1, b+t) + s(x, a-t-1, b-t-1);
			t--;
		}
		t = D-1;
		for(int x=v[i].x+1; x<=MAX_M3; x++){
			if(t<0)	break;
			ans += s(x, a+t, b+t) - s(x, a+t, b-t-1) - s(x, a-t-1, b+t) + s(x, a-t-1, b-t-1);
			t--;
		}
	}
	ans-=N;
	ans/=2;
	printf("%lld", ans);
	return;
}





int main(){
	scanf("%d%d%d%d", &B, &N, &D, &M);
	if(B==1){
		solve1();
	}else if(B==2){
		solve2();
	}else{
		solve3();
	}
	return 0;
}

Compilation message (stderr)

pairs.cpp: In function 'void solve1()':
pairs.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
pairs.cpp: In function 'void solve2()':
pairs.cpp:98:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<q.size(); i++){
               ~^~~~~~~~~
pairs.cpp: In function 'void solve1()':
pairs.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i]);
   ~~~~~^~~~~~~~~~~~~
pairs.cpp: In function 'void solve2()':
pairs.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &v[i].x, &v[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'void solve3()':
pairs.cpp:132:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].z);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:172:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &B, &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: 0 / 10
• Subtask 11: 10 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10