oj.uz

Submission #211714

# Submission time Handle Problem Language Result Execution time Memory
211714 2020-03-21T04:54:13 Z Lawliet Pairs (IOI07_pairs) C++17
100 / 100
 1572 ms 10640 KB 
#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

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

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1152 KB Output is correct
2 Correct 30 ms 1160 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1656 KB Output is correct
2 Correct 33 ms 1664 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1536 KB Output is correct
2 Correct 40 ms 1768 KB Output is correct
3 Correct 34 ms 1664 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 6 ms 1152 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10096 KB Output is correct
2 Correct 61 ms 10084 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 10220 KB Output is correct
2 Correct 73 ms 10220 KB Output is correct
3 Correct 69 ms 10212 KB Output is correct
4 Correct 70 ms 10340 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 10596 KB Output is correct
2 Correct 87 ms 10640 KB Output is correct
3 Correct 77 ms 10600 KB Output is correct
4 Correct 75 ms 10596 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Output is correct
2 Correct 19 ms 416 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 4332 KB Output is correct
2 Correct 236 ms 6376 KB Output is correct
3 Correct 235 ms 6384 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 4588 KB Output is correct
2 Correct 1229 ms 6632 KB Output is correct
3 Correct 1224 ms 6632 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 6628 KB Output is correct
2 Correct 1572 ms 6632 KB Output is correct
3 Correct 1549 ms 6632 KB Output is correct