Submission #1176108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176108		StefanSebez	Pairs (IOI07_pairs)	C++20	100 / 100	968 ms	65888 KiB

pairs

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int M=80050,M1=80,inf=2e9;
void Unique(vector<int>&a){sort(a.begin(),a.end());int m=unique(a.begin(),a.end())-a.begin();a.resize(m);}
int n,D;
void Solve1(){
	int a[n+10];
	for(int i=1;i<=n;i++) scanf("%i",&a[i]);
	sort(a+1,a+n+1);
	ll res=0;
	for(int i=1;i<=n;i++){
		int l=1,r=i,levo=i;
		while(l<=r){
			int mid=l+r>>1;
			if(a[i]-a[mid]<=D){levo=mid;r=mid-1;}
			else l=mid+1;
		}
		res+=i-levo;
	}
	printf("%lld\n",res);
}
struct Bit2d{
	vector<int>Vals[M+50],T[M+50];
	void Init(){for(int i=0;i<=M;i++){Vals[i].pb(-inf);Unique(Vals[i]);T[i].resize(Vals[i].size());}}
	void Ubaci(int i,int j){for(;i<=M;i+=i&-i)Vals[i].pb(j);}
	void Update(int i,int j,int x){for(;i<=M;i+=i&-i)Update1(i,j,x);}
	void Update1(int i,int j,int x){for(int k=upper_bound(Vals[i].begin(),Vals[i].end(),j)-Vals[i].begin()-1;k<Vals[i].size();k+=k&-k)T[i][k]+=x;}
	int Get(int i,int j){int x=0;for(;i>=1;i-=i&-i)x+=Get1(i,j);return x;}
	int Get1(int i,int j){int x=0;for(int k=upper_bound(Vals[i].begin(),Vals[i].end(),j)-Vals[i].begin()-1;k>=1;k-=k&-k)x+=T[i][k];return x;}
	int Get(int l,int L,int r,int R){return Get(L,R)-Get(l-1,R)-Get(L,r-1)+Get(l-1,r-1);}
}bt2[2];
void Solve2(){
	array<int,2>a[n+10];
	for(int i=1;i<=n;i++) scanf("%i%i",&a[i][0],&a[i][1]);
    sort(a+1,a+n+1);
    ll res=0;
    for(int i=1;i<=n;i++){
		int x=a[i][0],y=a[i][1];
		bt2[0].Ubaci(y,x+y);
		bt2[1].Ubaci(y,x-y);
    }
    bt2[0].Init(),bt2[1].Init();
    for(int i=1;i<=n;i++){
		int x=a[i][0],y=a[i][1];
		res+=bt2[0].Get(0,y,x+y-D,inf);
		res+=bt2[1].Get(y+1,M,x-y-D,inf);
		bt2[0].Update(y,x+y,1);
		bt2[1].Update(y,x-y,1);
    }
    printf("%lld\n",res);
}
struct Bit3d{
	vector<int>Vals[M1+2][M1+2],T[M1+2][M1+2];
	void Init(){for(int i=0;i<=M1;i++)for(int j=0;j<=M1;j++){Vals[i][j].pb(-inf);Unique(Vals[i][j]);T[i][j].resize(Vals[i][j].size());}}
	void Ubaci(int i,int j,int k){for(;i<=M1;i+=i&-i)for(int l=j;l<=M1;l+=l&-l)Vals[i][l].pb(k);}
	void Update(int i,int j,int k,int x){for(;i<=M1;i+=i&-i)for(int l=j;l<=M1;l+=l&-l)Update1(i,l,k,x);}
	void Update1(int i,int j,int k,int x){for(int l=upper_bound(Vals[i][j].begin(),Vals[i][j].end(),k)-Vals[i][j].begin()-1;l<Vals[i][j].size();l+=l&-l)T[i][j][l]+=x;}
	int Get(int i,int j,int k){int x=0;for(;i>=1;i-=i&-i)for(int l=j;l>=1;l-=l&-l)x+=Get1(i,l,k);return x;}
	int Get1(int i,int j,int k){int x=0;for(int l=upper_bound(Vals[i][j].begin(),Vals[i][j].end(),k)-Vals[i][j].begin()-1;l>=1;l-=l&-l)x+=T[i][j][l];return x;}
	int Get(int x,int X,int y,int Y,int z,int Z){x--,y--,z--;return Get(X,Y,Z)-Get(x,Y,Z)-Get(X,y,Z)-Get(X,Y,z)+Get(x,y,Z)+Get(x,Y,z)+Get(X,y,z)-Get(x,y,z);}
}bt3[4];
void Solve3(){
	array<int,3>a[n+10];
	for(int i=1;i<=n;i++) scanf("%i%i%i",&a[i][0],&a[i][1],&a[i][2]);
	sort(a+1,a+n+1);
	ll res=0;
	for(int i=1;i<=n;i++){
		int x=a[i][0],y=a[i][1],z=a[i][2];
		bt3[0].Ubaci(y,z,x+y+z);
		bt3[1].Ubaci(y,z,x-y+z);
		bt3[2].Ubaci(y,z,x+y-z);
		bt3[3].Ubaci(y,z,x-y-z);
	}
	for(int i=0;i<4;i++) bt3[i].Init();
	for(int i=1;i<=n;i++){
		int x=a[i][0],y=a[i][1],z=a[i][2];
		res+=bt3[0].Get(0,y,0,z,x+y+z-D,inf);
		res+=bt3[1].Get(y+1,M1,0,z,x-y+z-D,inf);
		res+=bt3[2].Get(0,y,z+1,M1,x+y-z-D,inf);
		res+=bt3[3].Get(y+1,M1,z+1,M1,x-y-z-D,inf);
		bt3[0].Update(y,z,x+y+z,1);
		bt3[1].Update(y,z,x-y+z,1);
		bt3[2].Update(y,z,x+y-z,1);
		bt3[3].Update(y,z,x-y-z,1);
	}
	printf("%lld\n",res);
}
int main(){
    int B,mm;scanf("%i%i%i%i",&B,&n,&D,&mm);
    if(B==1)Solve1();
    if(B==2)Solve2();
    if(B==3)Solve3();
    return 0;
}

Compilation message (stderr)

pairs.cpp: In function 'void Solve1()':
pairs.cpp:13:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         for(int i=1;i<=n;i++) scanf("%i",&a[i]);
      |                               ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void Solve2()':
pairs.cpp:39:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         for(int i=1;i<=n;i++) scanf("%i%i",&a[i][0],&a[i][1]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'void Solve3()':
pairs.cpp:69:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         for(int i=1;i<=n;i++) scanf("%i%i%i",&a[i][0],&a[i][1],&a[i][2]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:94:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     int B,mm;scanf("%i%i%i%i",&B,&n,&D,&mm);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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