Submission #211714

#	Time	Username	Problem	Language	Result	Execution time	Memory
211714		Lawliet	Pairs (IOI07_pairs)	C++17	100 / 100	1572 ms	10640 KiB

pairs

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 100010;
const int MAXV = 2000010;

struct event
{
	int type;
	int x, y1, y2;

	event(int x, int y1, int y2, int t)
		: x(x), y1(y1), y2(y2), type(t) {}

	bool operator < (event a)
	{
		if( x != a.x ) return x < a.x;
		return type < a.type;
	}
};

class FenwickTree
{
	public:

		void update(int i)
		{
			for( ; i <= N ; i += i & -i )
				BIT[i]++;
		}

		int query(int i)
		{
			int ans = 0;

			for( ; i > 0 ; i -= i & -i )
				ans += BIT[i];

			return ans;
		}

		void init(int n)
		{
			N = n;

			for(int i = 1 ; i <= n ; i++)
				BIT[i] = 0;
		}

		int sum(int L, int R) { return query(R) - query(L - 1); }

	private:

		int N;
		int BIT[MAXV];
};

int subtask;
int n, d, m;

int x[MAXN];
int y[MAXN];
int z[MAXN];

lli ans;

vector< event > sweep;

FenwickTree BIT;

void solveSubtask1()
{
	for(int i = 1 ; i <= n ; i++)
		scanf("%d",&x[i]);

	sort( x + 1 , x + n + 1 );

	for(int i = 1 ; i <= n ; i++)
	{
		int L = lower_bound( x + 1 , x + n + 1 , x[i] - d ) - x;
		int R = upper_bound( x + 1 , x + n + 1 , x[i] + d ) - x - 1;

		ans += R - L + 1;
	}
}

void createQuery(int i)
{
	event query( x[i] + y[i] , x[i] - y[i] , y[i] , 1 );
	sweep.push_back( query );
}

void createUpdate(int i, int curZ)
{
	int dZ = d - abs( curZ - z[i] );

	if( dZ < 0 ) return;

	event add( x[i] + y[i] - dZ , x[i] - y[i] - dZ , x[i] - y[i] + dZ , 0 );
	event remove( x[i] + y[i] + dZ , x[i] - y[i] - dZ , x[i] - y[i] + dZ , 2 );

	sweep.push_back( add );
	sweep.push_back( remove );
}

void solveSubtask3()
{
	int maxZ = 0;
	
	for(int i = 1 ; i <= n ; i++)
	{
		scanf("%d %d",&x[i],&y[i]);
		if( subtask == 3 ) scanf("%d",&z[i]);

		maxZ = max( maxZ , z[i] );
	}

	for(int curZ = 0 ; curZ <= maxZ ; curZ++)
	{
		sweep.clear();

		for(int i = 1 ; i <= n ; i++)
		{
			if( z[i] == curZ ) createQuery( i );
			createUpdate( i , curZ );
		}

		int minY = 0;
		int maxY = 0;

		for(int i = 0 ; i < sweep.size() ; i++)
			minY = min( minY , sweep[i].y1 );

		for(int i = 0 ; i < sweep.size() ; i++)
		{
			sweep[i].y1 -= minY - 1;
			sweep[i].y2 -= minY - 1;

			maxY = max( maxY , sweep[i].y1 );
			maxY = max( maxY , sweep[i].y2 );
		}

		BIT.init( maxY );

		sort( sweep.begin() , sweep.end() );

		for(int i = 0 ; i < sweep.size() ; i++)
		{
			int y1 = sweep[i].y1;
			int y2 = sweep[i].y2;
			int type = sweep[i].type;

			if( type == 0 ) ans -= BIT.sum( y1 , y2 );
			if( type == 1 ) BIT.update( y1 );
			if( type == 2 ) ans += BIT.sum( y1 , y2 );
		}
	}
}

int main()
{
	scanf("%d",&subtask);
	scanf("%d %d %d",&n,&d,&m);

	if( subtask == 1 ) solveSubtask1();
	if( subtask == 2 || subtask == 3 ) solveSubtask3();

	ans -= n;
	printf("%lld\n",ans/2);
}

Compilation message (stderr)

pairs.cpp: In constructor 'event::event(int, int, int, int)':
pairs.cpp:12:13: warning: 'event::y2' will be initialized after [-Wreorder]
  int x, y1, y2;
             ^~
pairs.cpp:11:6: warning:   'int event::type' [-Wreorder]
  int type;
      ^~~~
pairs.cpp:14:2: warning:   when initialized here [-Wreorder]
  event(int x, int y1, int y2, int t)
  ^~~~~
pairs.cpp: In function 'void solveSubtask3()':
pairs.cpp:133:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < sweep.size() ; i++)
                   ~~^~~~~~~~~~~~~~
pairs.cpp:136:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < sweep.size() ; i++)
                   ~~^~~~~~~~~~~~~~
pairs.cpp:149:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < sweep.size() ; i++)
                   ~~^~~~~~~~~~~~~~
pairs.cpp: In function 'void solveSubtask1()':
pairs.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x[i]);
   ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'void solveSubtask3()':
pairs.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
pairs.cpp:115:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if( subtask == 3 ) scanf("%d",&z[i]);
                      ~~~~~^~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&subtask);
  ~~~~~^~~~~~~~~~~~~~~
pairs.cpp:165:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&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: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10