oj.uz

Submission #411726

# Submission time Handle Problem Language Result Execution time Memory
411726 2021-05-25T19:18:22 Z Jasiekstrz Pairs (IOI07_pairs) C++17
100 / 100
 1134 ms 16700 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
namespace d1
{
	int tab[N+10];
	long long solve()
	{
		int n,d,m;
		cin>>n>>d>>m;
		for(int i=1;i<=n;i++)
			cin>>tab[i];
		sort(tab+1,tab+n+1);
		long long ans=0;
		for(int i=1,j=1;i<=n;i++)
		{
			while(tab[i]-tab[j]>d)
				j++;
			ans+=i-j;
		}
		return ans;
	}
};
namespace d2
{
	const int P=27e4;
	struct Event
	{
		int x,y;
		int val;
		bool operator<(const Event &oth)
		{
			return x<oth.x;
		}
	};
	pair<int,int> tab[N+10];
	vector<Event> ev;
	int pot;
	int tree[2*P+10];
	void add(int x,int c)
	{
		for(x+=pot-1;x>0;x/=2)
			tree[x]+=c;
		return;
	}
	long long read(int l,int r)
	{
		l=max(1,l);r=min(pot,r);
		long long ans=0;
		for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
		{
			if(l%2==1)
				ans+=tree[l++];
			if(r%2==0)
				ans+=tree[r--];
		}
		return ans;
	}
	long long solve()
	{
		int n,d,m;
		cin>>n>>d>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>tab[i].fi>>tab[i].se;
			ev.push_back({tab[i].fi-tab[i].se,tab[i].fi+tab[i].se,1});
			ev.push_back({tab[i].fi-tab[i].se+d+1,tab[i].fi+tab[i].se,-1});
		}
		sort(ev.begin(),ev.end());
		for(pot=1;pot<2*m;pot++);
		long long ans=0;
		for(int i=-m,j=0;i<=m;i++)
		{
			size_t it;
			for(it=j;it<ev.size() && ev[it].x==i;it++)
			{
				if(ev[it].val==-1)
					add(ev[it].y,ev[it].val);
			}
			for(it=j;it<ev.size() && ev[it].x==i;it++)
			{
				if(ev[it].val==1)
				{
					ans+=read(ev[it].y-d,ev[it].y+d);
					add(ev[it].y,ev[it].val);
					//cerr<<ev[it].x<<" "<<ev[it].y<<" ["<<ans<<"]\n";
				}
			}
			j=it;
		}
		return ans;
	}
};
namespace d3
{
	const int M=75;
	int pref[M+10][2*M+10][2*M+10];
	int tab[M+10][2*M+10][2*M+10];
	vector<tuple<int,int,int>> t;
	int read(int a,int b,int c)
	{
		if(a<0 || b<0 || c<0)
			return 0;
		a=min(a,M);
		b=min(b,2*M);
		c=min(c,2*M);
		return pref[a][b][c];
	}
	long long read_d(int a,int b,int c,int d)
	{
		d++;
		return read(a,b,c)-read(a,b-d,c)-read(a,b,c-d)+read(a,b-d,c-d);
	}
	long long solve()
	{
		int n,m,d;
		cin>>n>>d>>m;
		long long ans=0;
		for(int i=1;i<=n;i++)
		{
			int a,b,c;
			cin>>a>>b>>c;
			tab[a][b+c][b-c+m]++;
			ans-=tab[a][b+c][b-c+m];
			t.emplace_back(a,b+c,b-c+m);
		}
		for(int i=1;i<=M;i++)
		{
			for(int j=1;j<=2*M;j++)
			{
				for(int k=1;k<=2*M;k++)
				{
					pref[i][j][k]=tab[i][j][k]+read(i,j-1,k)+read(i,j,k-1)-read(i,j-1,k-1);
				}
			}
		}
		for(auto [a,b,c]:t)
		{
			for(int i=1;i<=m;i++)
			{
				if(abs(a-i)>d)
					continue;
				ans+=read_d(i,b,c,d-abs(a-i))+read_d(i,b-1,c+d-abs(a-i),d-abs(a-i)-1);
				if(i>a)
					ans-=tab[i][b][c];
			}
		}
		return ans;
	}
};
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int board_type;
	cin>>board_type;
	if(board_type==1)
		cout<<d1::solve();
	else if(board_type==2)
		cout<<d2::solve();
	else
		cout<<d3::solve();
	cout<<"\n";
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 684 KB Output is correct
2 Correct 15 ms 708 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 588 KB Output is correct
2 Correct 20 ms 720 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 716 KB Output is correct
2 Correct 21 ms 700 KB Output is correct
3 Correct 20 ms 616 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1484 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4032 KB Output is correct
2 Correct 33 ms 4068 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4012 KB Output is correct
2 Correct 45 ms 4032 KB Output is correct
3 Correct 43 ms 4032 KB Output is correct
4 Correct 44 ms 4040 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4620 KB Output is correct
2 Correct 73 ms 4576 KB Output is correct
3 Correct 52 ms 4568 KB Output is correct
4 Correct 57 ms 4604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10344 KB Output is correct
2 Correct 33 ms 10432 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 9088 KB Output is correct
2 Correct 82 ms 8904 KB Output is correct
3 Correct 72 ms 9600 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 13484 KB Output is correct
2 Correct 641 ms 14324 KB Output is correct
3 Correct 378 ms 14264 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 15796 KB Output is correct
2 Correct 1134 ms 16696 KB Output is correct
3 Correct 700 ms 16700 KB Output is correct