oj.uz

Submission #93193

# Submission time Handle Problem Language Result Execution time Memory
93193 2019-01-07T06:15:37 Z antimirage Chessboard (IZhO18_chessboard) C++14
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()
 
using namespace std;

const int N = 1e5 + 5;

int m, x1[N], y1[N], x2[N], y2[N];

long long n, ans = 1e18;

long long compute (int j1, int j2, long long bl)
{
	if (j1 / bl == j2 / bl)
	{
		if (j1 / bl & 1)
			return (j2 - j1 + 1);
		
		return 0ll;
	}
	long long res = 0;
	
	if (j1 / bl & 1)
		res += (j1 / bl * bl + bl - j1);
	
	j1 = j1 / bl * bl + bl;
	
	if (j2 / bl & 1)
		res += (j2 % bl + 1);
		
	j2 = j2 / bl * bl - 1;
	
	long long cn = (j2 / bl - j1 / bl + 1) / 2;
	
	if ( ((j2 / bl - j1 / bl + 1) & 1) && (j2 / bl & 1) )
		cn++;
	
	res += cn * bl;
	return res;
}

long long get (int i1, int j1, int i2, int j2, long long bl)
{
	long long res = 0, cn1 = compute( j1, j2, bl ), cn2 = (j2 - j1 + 1) - cn1;
	
	if (i1 / bl == i2 / bl)
	{
		if (i1 / bl & 1)
			res += cn1 * (i2 - i1 + 1);
		else
			res += cn2 * (i2 - i1 + 1);
	}
	else
	{
		if (i1 / bl & 1)
			res += cn1 * (i1 / bl * bl + bl - i1);
		else
			res += cn2 * (i1 / bl * bl + bl - i1);
			
		i1 = i1 / bl * bl + bl;
		
		if (i2 / bl & 1)
			res += cn1 * (i2 % bl + 1);
		else
			res += cn2 * (i2 % bl + 1);
			
		i2 = i2 / bl * bl - 1;
		
		long long cn = (i2 / bl - i1 / bl + 1) / 2;
		
		if ( (i2 / bl - i1 / bl + 1) & 1 )
		{
			if ( i1 / bl % 2 == 0 )
			{
				res += (cn + 1) * cn2 * bl;
				res += cn * cn1 * bl;
			}
			else
			{
				res += (cn + 1) * cn1 * bl;
				res += cn * cn2 * bl;
			}
		}
		else
		{
			res += cn * cn1 * bl;
			res += cn * cn2 * bl;
		}
	}
	return res;
}

void calc (long long x)
{
	long long res = get(0, 0, n - 1, n - 1, x) ;
	
	for (int i = 1; i <= m; i++)
	{
		long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
		res -= sup;
		res += ( (x2[i] - x1[i] + 1) * 1ll * (y2[i] - y1[i] + 1) - sup);
	}
	ans = min(ans, res);
	ans = min(ans, n * n - res);
}

main() 
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
		x1[i]--;
		y1[i]--;
		x2[i]--;
		y2[i]--;
	}
	for (long long i = 1; i * i <= n; i++)
	{
		if ( n % i != 0 ) continue;
		calc(i);
		if (n / i != n)
			calc(n / i);
	}
	cout << ans << endl;
}
/**
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6
**/

Compilation message

chessboard.cpp:13:19: error: 'int y1 [100005]' redeclared as different kind of symbol
 int m, x1[N], y1[N], x2[N], y2[N];
                   ^
In file included from /usr/include/features.h:367:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/c++config.h:533,
                 from /usr/include/c++/7/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from chessboard.cpp:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:251:1: note: previous declaration 'double y1(double)'
 __MATHCALL (y1,, (_Mdouble_));
 ^
chessboard.cpp: In function 'void calc(long long int)':
chessboard.cpp:104:35: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                   ^
chessboard.cpp:104:53: error: no matching function for call to 'get(int&, double (&)(double) throw (), int&, int&, long long int&)'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
chessboard.cpp:47:11: note: candidate: long long int get(int, int, int, int, long long int) <near match>
 long long get (int i1, int j1, int i2, int j2, long long bl)
           ^~~
chessboard.cpp:47:11: note:   conversion of argument 2 would be ill-formed:
chessboard.cpp:104:35: error: invalid conversion from 'double (*)(double) throw ()' to 'int' [-fpermissive]
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                               ~~~~^
In file included from /usr/include/c++/7/functional:54:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from chessboard.cpp:1:
/usr/include/c++/7/tuple:1361:5: note: candidate: template<class _Tp, class ... _Types> constexpr const _Tp& std::get(const std::tuple<_Elements ...>&)
     get(const tuple<_Types...>& __t) noexcept
     ^~~
/usr/include/c++/7/tuple:1361:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'const std::tuple<_Elements ...>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/functional:54:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from chessboard.cpp:1:
/usr/include/c++/7/tuple:1355:5: note: candidate: template<class _Tp, class ... _Types> constexpr _Tp&& std::get(std::tuple<_Elements ...>&&)
     get(tuple<_Types...>&& __t) noexcept
     ^~~
/usr/include/c++/7/tuple:1355:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::tuple<_Elements ...>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/functional:54:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from chessboard.cpp:1:
/usr/include/c++/7/tuple:1349:5: note: candidate: template<class _Tp, class ... _Types> constexpr _Tp& std::get(std::tuple<_Elements ...>&)
     get(tuple<_Types...>& __t) noexcept
     ^~~
/usr/include/c++/7/tuple:1349:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::tuple<_Elements ...>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/functional:54:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from chessboard.cpp:1:
/usr/include/c++/7/tuple:1326:5: note: candidate: template<long unsigned int __i, class ... _Elements> constexpr std::__tuple_element_t<__i, std::tuple<_Elements ...> >&& std::get(std::tuple<_Elements ...>&&)
     get(tuple<_Elements...>&& __t) noexcept
     ^~~
/usr/include/c++/7/tuple:1326:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::tuple<_Elements ...>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/functional:54:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from chessboard.cpp:1:
/usr/include/c++/7/tuple:1320:5: note: candidate: template<long unsigned int __i, class ... _Elements> constexpr std::__tuple_element_t<__i, std::tuple<_Elements ...> >& std::get(const std::tuple<_Elements ...>&)
     get(const tuple<_Elements...>& __t) noexcept
     ^~~
/usr/include/c++/7/tuple:1320:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'const std::tuple<_Elements ...>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/functional:54:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from chessboard.cpp:1:
/usr/include/c++/7/tuple:1314:5: note: candidate: template<long unsigned int __i, class ... _Elements> constexpr std::__tuple_element_t<__i, std::tuple<_Elements ...> >& std::get(std::tuple<_Elements ...>&)
     get(tuple<_Elements...>& __t) noexcept
     ^~~
/usr/include/c++/7/tuple:1314:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::tuple<_Elements ...>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/tuple:39:0,
                 from /usr/include/c++/7/functional:54,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from chessboard.cpp:1:
/usr/include/c++/7/array:324:5: note: candidate: template<long unsigned int _Int, class _Tp, long unsigned int _Nm> constexpr const _Tp& std::get(const std::array<_Tp, _Nm>&)
     get(const array<_Tp, _Nm>& __arr) noexcept
     ^~~
/usr/include/c++/7/array:324:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'const std::array<_Tp, _Nm>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/tuple:39:0,
                 from /usr/include/c++/7/functional:54,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from chessboard.cpp:1:
/usr/include/c++/7/array:316:5: note: candidate: template<long unsigned int _Int, class _Tp, long unsigned int _Nm> constexpr _Tp&& std::get(std::array<_Tp, _Nm>&&)
     get(array<_Tp, _Nm>&& __arr) noexcept
     ^~~
/usr/include/c++/7/array:316:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::array<_Tp, _Nm>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/tuple:39:0,
                 from /usr/include/c++/7/functional:54,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from chessboard.cpp:1:
/usr/include/c++/7/array:307:5: note: candidate: template<long unsigned int _Int, class _Tp, long unsigned int _Nm> constexpr _Tp& std::get(std::array<_Tp, _Nm>&)
     get(array<_Tp, _Nm>& __arr) noexcept
     ^~~
/usr/include/c++/7/array:307:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::array<_Tp, _Nm>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/algorithm:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from chessboard.cpp:1:
/usr/include/c++/7/utility:273:5: note: candidate: template<class _Tp, class _Up> constexpr _Tp&& std::get(std::pair<_Up, _Tp>&&)
     get(pair<_Up, _Tp>&& __p) noexcept
     ^~~
/usr/include/c++/7/utility:273:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::pair<_Up, _Tp>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/algorithm:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from chessboard.cpp:1:
/usr/include/c++/7/utility:268:5: note: candidate: template<class _Tp, class _Up> constexpr const _Tp& std::get(const std::pair<_Up, _Tp>&)
     get(const pair<_Up, _Tp>& __p) noexcept
     ^~~
/usr/include/c++/7/utility:268:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'const std::pair<_Up, _Tp>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/algorithm:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from chessboard.cpp:1:
/usr/include/c++/7/utility:263:5: note: candidate: template<class _Tp, class _Up> constexpr _Tp& std::get(std::pair<_Up, _Tp>&)
     get(pair<_Up, _Tp>& __p) noexcept
     ^~~
/usr/include/c++/7/utility:263:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::pair<_Up, _Tp>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/algorithm:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from chessboard.cpp:1:
/usr/include/c++/7/utility:258:5: note: candidate: template<class _Tp, class _Up> constexpr _Tp&& std::get(std::pair<_T1, _T2>&&)
     get(pair<_Tp, _Up>&& __p) noexcept
     ^~~
/usr/include/c++/7/utility:258:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::pair<_T1, _T2>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/algorithm:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from chessboard.cpp:1:
/usr/include/c++/7/utility:253:5: note: candidate: template<class _Tp, class _Up> constexpr const _Tp& std::get(const std::pair<_T1, _T2>&)
     get(const pair<_Tp, _Up>& __p) noexcept
     ^~~
/usr/include/c++/7/utility:253:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'const std::pair<_T1, _T2>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/algorithm:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from chessboard.cpp:1:
/usr/include/c++/7/utility:248:5: note: candidate: template<class _Tp, class _Up> constexpr _Tp& std::get(std::pair<_T1, _T2>&)
     get(pair<_Tp, _Up>& __p) noexcept
     ^~~
/usr/include/c++/7/utility:248:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::pair<_T1, _T2>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/algorithm:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from chessboard.cpp:1:
/usr/include/c++/7/utility:239:5: note: candidate: template<long unsigned int _Int, class _Tp1, class _Tp2> constexpr const typename std::tuple_element<_Int, std::pair<_Tp1, _Tp2> >::type& std::get(const std::pair<_Tp1, _Tp2>&)
     get(const std::pair<_Tp1, _Tp2>& __in) noexcept
     ^~~
/usr/include/c++/7/utility:239:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'const std::pair<_Tp1, _Tp2>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/algorithm:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from chessboard.cpp:1:
/usr/include/c++/7/utility:234:5: note: candidate: template<long unsigned int _Int, class _Tp1, class _Tp2> constexpr typename std::tuple_element<_Int, std::pair<_Tp1, _Tp2> >::type&& std::get(std::pair<_Tp1, _Tp2>&&)
     get(std::pair<_Tp1, _Tp2>&& __in) noexcept
     ^~~
/usr/include/c++/7/utility:234:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::pair<_Tp1, _Tp2>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
In file included from /usr/include/c++/7/algorithm:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from chessboard.cpp:1:
/usr/include/c++/7/utility:229:5: note: candidate: template<long unsigned int _Int, class _Tp1, class _Tp2> constexpr typename std::tuple_element<_Int, std::pair<_Tp1, _Tp2> >::type& std::get(std::pair<_Tp1, _Tp2>&)
     get(std::pair<_Tp1, _Tp2>& __in) noexcept
     ^~~
/usr/include/c++/7/utility:229:5: note:   template argument deduction/substitution failed:
chessboard.cpp:104:53: note:   mismatched types 'std::pair<_Tp1, _Tp2>' and 'int'
   long long sup = get( x1[i], y1[i], x2[i], y2[i], x);
                                                     ^
chessboard.cpp:106:53: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   res += ( (x2[i] - x1[i] + 1) * 1ll * (y2[i] - y1[i] + 1) - sup);
                                                     ^
chessboard.cpp:106:47: error: invalid operands of types 'int' and 'double(double) throw ()' to binary 'operator-'
   res += ( (x2[i] - x1[i] + 1) * 1ll * (y2[i] - y1[i] + 1) - sup);
                                         ~~~~~~^~~~~~~
chessboard.cpp: At global scope:
chessboard.cpp:112:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() 
      ^
chessboard.cpp: In function 'int main()':
chessboard.cpp:117:37: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
                                     ^
chessboard.cpp:117:54: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'double (*)(double) throw ()' [-Wformat=]
   scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
                                ~~~~~~                ^
chessboard.cpp:119:7: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   y1[i]--;
       ^
chessboard.cpp:119:8: warning: ISO C++ forbids decrementing a pointer of type 'double (*)(double) throw ()' [-Wpointer-arith]
   y1[i]--;
        ^~
chessboard.cpp:119:8: error: lvalue required as decrement operand
chessboard.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~