Submission #94911

#	Time	Username	Problem	Language	Result	Execution time	Memory
94911		Retro3014	Pairs (IOI07_pairs)	C++17	60 / 100	207 ms	13664 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;
}

void solve3(){
	printf("0");
	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 'int main()':
pairs.cpp:119: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: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10