/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )
/▄/ /█/ /◐/ /▐/ /▌/ /▀/ /░/ /🔥/ choose own style!
***IT'S OUR LONG WAY TO THE OIILLLL***
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma comment(linker, "/stack:200000000")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ld long doubl
#define fi first
#define se second
#define eb emplace_back
#define pii pair < int , int >
#define pipii pair< int, pair < int , int > >
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/detail/standard_policies.hpp>'
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container){for (auto &u : container)os << u << " ";return os;}template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << p.first << " " << p.second; }template <class T> ostream &operator<<(ostream &os, set<T> const& con) { for (auto &u : con) os << u << " "; return os; }void pr() {}template <typename T, typename... args> void pr(T x, args... tail) { cout << x << " "; pr(tail...);}}using namespace fastio;
const int N = 3e5 + 5;
const int MA = 1e6 + 1;
const int X[4] = {0, 0, 1, -1};
const int Y[4] = {-1, 1, 0, 0};
vector < int > g[N];
ll n, k;
vector < pair < pii , pii > > q(N);
int x1, yy1, x2, y2;
int kk[4];
void update(pair < pii , pii > q, int len)
{
x1 = q.fi.fi;
x2 = q.se.fi;
yy1 = q.fi.se;
y2 = q.se.se;
kk[0] = x1 % len;
if (kk[0])
kk[0] = len - kk[0];
kk[0] = min(kk[0], x2 - x1 + 1);
kk[1] = (x2 + 1) % len;
kk[1] = min(kk[1], x2 - x1 + 1);
kk[2] = yy1 % len;
if (kk[2])
kk[2] = len - kk[2];
kk[2] = min(kk[2], y2 - yy1 + 1);
kk[3] = (y2 + 1) % len;
kk[3] = min(kk[3], y2 - yy1 + 1);
}
ll solve(int len)
{
ll all = n * n;
ll ans = 0;
int llen = len * 2;
vector < pair < pii , pii > > z = q;
for (int i = 0; i < n; ++i)
if (i % llen < len)
ans += (n / len / 2 + (n / len) % 2) * 1ll * len; else
ans += (n / len / 2) * 1ll * len;
for (int i = 0; i < k; ++i)
{
//kk[4]
update(q[i], len);
// cout<<ans<<endl;
if (kk[2])
{
ll otv = 0;
if (((x1 % llen < len) + (yy1 % llen < len)) % 2 == 0)
otv -= kk[0]; else otv += kk[0];
if (x1 / len != x2 / len || (!kk[0]))
if (((x2 % llen < len) + (yy1 % llen < len)) % 2 == 0)
otv -= kk[1]; else otv += kk[1];
ll dis = x2 - x1 + 1 - kk[0] - kk[1];
ll bx = dis / len / 2 + (dis / len) % 2;
ll mx = dis / len / 2;
if ((1 + (yy1 % llen < len)) % 2 == 0)
otv -= len * bx,
otv += len * mx; else
otv += len * bx,
otv -= len * mx;
ans += otv * kk[2];
q[i].fi.se += kk[2];
}
if (q[i].fi.fi > q[i].se.fi || q[i].fi.se > q[i].se.se) continue;
update(q[i], len);
if (kk[0])
{
ll otv = 0;
if (((x1 % llen < len) + (y2 % llen < len)) % 2 == 0)
otv -= kk[3]; else otv += kk[3];
ll dis = y2 - yy1 + 1 - kk[3];
ll bx = dis / len / 2 + (dis / len) % 2;
ll mx = dis / len / 2;
if (((x1 % llen < len) + (yy1 % llen < len)) % 2 == 0)
otv -= len * bx,
otv += len * mx; else
otv += len * bx,
otv -= len * mx;
ans += otv * kk[0];
q[i].fi.fi += kk[0];
}
if (q[i].fi.fi > q[i].se.fi || q[i].fi.se > q[i].se.se) continue;
update(q[i], len);
if (kk[3])
{
ll otv = 0;
if (((x2 % llen < len) + (y2 % llen < len)) % 2 == 0)
otv -= kk[1]; else otv += kk[1];
ll dis = x2 - x1 + 1 - kk[1];
ll bx = dis / len / 2 + (dis / len) % 2;
ll mx = dis / len / 2;
if (((x1 % llen < len) + (y2 % llen < len)) % 2 == 0)
otv -= len * bx,
otv += len * mx; else
otv += len * bx,
otv -= len * mx;
ans += otv * kk[3];
q[i].se.se -= kk[3];
}
if (q[i].fi.fi > q[i].se.fi || q[i].fi.se > q[i].se.se) continue;
update(q[i], len);
// cout<<kk[0]<<" "<<kk[1]<<" "<<kk[2]<<" "<<kk[3]<<endl;
if (kk[1])
{
ll otv = 0;
ll dis = y2 - yy1 + 1;
ll bx = dis / len / 2 + (dis / len) % 2;
ll mx = dis / len / 2;
if (((x2 % llen < len) + (yy1 % llen < len)) % 2 == 0)
otv -= len * bx,
otv += len * mx; else
otv += len * bx,
otv -= len * mx;
// cout<<otv<<endl;
ans += otv * kk[1];
q[i].se.fi -= kk[1];
}
if (q[i].fi.fi > q[i].se.fi || q[i].fi.se > q[i].se.se) continue;
update(q[i], len);
//right
ll dx = q[i].se.fi - q[i].fi.fi + 1;
ll dy = q[i].se.se - q[i].fi.se + 1;
ll by = dy / len / 2 + (dy / len) % 2;
ll my = dy / len / 2;
ll bx = dx / len / 2 + (dx / len) % 2;
ll mx = dx / len / 2;
ll alll = dx * dy;
int nac = (q[i].fi.fi % llen < len) + (q[i].fi.se % llen < len);
// cout<<len<<" "<<nac<<" "<<dx<<" "<<dy<<" "<<mx<<" "<<my<<" "<<bx<<" "<<by<<" "<<ans<<endl;
if (nac % 2 == 0)
{
ll ch = (bx * by + mx * my) * 1ll * len * len;
ans -= ch;
ans += (alll - ch);
} else
{
ll ch = (mx * by + bx * my) * 1ll * len * len;
ans -= ch;
ans += (alll - ch);
}
}
// cout<<ans<<endl;
// cout<<ans<<endl;
// cout<<all<<endl;
// cout<<endl;
q = z;
cout<<ans<<endl;
cout << min(all - ans, ans)<<endl;
cout<<endl;
return min(ans, all - ans);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Estb_probitie
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
cin >> n >> k;
for (int i = 0; i < k; ++i)
{
int x1, x2, yy1, y2;
cin >> x1 >> yy1 >> x2 >> y2;
--x1, --x2, --yy1, --y2;
q[i] = {{x1, yy1}, {x2, y2}};
}
ll ans = solve(1);
for (int i = 2; i * i <= n; ++i)
if (n % i == 0)
{
ans = min(ans, solve(i));
ans = min(ans, solve(n / i));
}
cout << ans;
}
Compilation message
chessboard.cpp: In function 'long long int solve(int)':
chessboard.cpp:113:16: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if (x1 / len != x2 / len || (!kk[0]))
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
16760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
16800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
16800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
16760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
