oj.uz

Submission #94931

# Submission time Handle Problem Language Result Execution time Memory
94931 2019-01-25T09:47:09 Z Retro3014 Pairs (IOI07_pairs) C++17
100 / 100
 246 ms 12548 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 252 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 760 KB Output is correct
2 Correct 23 ms 1148 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 760 KB Output is correct
2 Correct 23 ms 760 KB Output is correct
3 Correct 22 ms 760 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 508 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 7784 KB Output is correct
2 Correct 104 ms 7800 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 7784 KB Output is correct
2 Correct 143 ms 7840 KB Output is correct
3 Correct 145 ms 7780 KB Output is correct
4 Correct 144 ms 7804 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 12548 KB Output is correct
2 Correct 182 ms 12468 KB Output is correct
3 Correct 132 ms 8128 KB Output is correct
4 Correct 139 ms 8032 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7032 KB Output is correct
2 Correct 12 ms 7188 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8320 KB Output is correct
2 Correct 54 ms 8364 KB Output is correct
3 Correct 69 ms 8312 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 8312 KB Output is correct
2 Correct 208 ms 8336 KB Output is correct
3 Correct 113 ms 9208 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 8312 KB Output is correct
2 Correct 246 ms 9160 KB Output is correct
3 Correct 117 ms 9208 KB Output is correct