제출 #155531

#제출 시각아이디문제언어결과실행 시간메모리
155531Dasha_GnedkoChessboard (IZhO18_chessboard)C++14
100 / 100
1975 ms2040 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/detail/standard_policies.hpp> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4") #define ll long long #define ld long double #define pb push_back #define F first #define S second #define endl '\n' //#define int long long using namespace std; //using namespace __gnu_pbds; //template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>; const int N = 1e5 + 100; const int M = 21890; const ll mod = 1e9 + 7; const ll MOD = 998244353; const int P = 1336; const ld eps = 0.000000001; const int inf = 1e9 + 7; const ll inff = 1e18 + 7; mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count()); int l1[N], r1[N], l2[N], r2[N]; int m; vector <int> a; pair <int, pair <ll, ll> > get(ll r, ll x, ll y, int fl) { ll gx = x / r, gy = y / r; if (x % r) gx++; if (y % r) gy++; bool f; if (fl == 0) { if (gx % 2) { if (gy % 2) f = 0; else f = 1; } else if (gy % 2) f = 1; else f = 0; } else { if (gx % 2) { if (gy % 2) f = 1; else f = 0; } else if (gy % 2) f = 0; else f = 1; } ll bx = 1ll * gx * r - x + 1; ll by = 1ll * gy * r - y + 1; return {f, {bx, by}}; } ll solve(ll r, ll x1, ll y1, ll x2, ll y2, int fl) { if (x1 > x2 || y1 > y2) return 0; ll gx1 = x1 / r + 1, gx2 = x2 / r; if (x1 % r != 1) gx1++; if (x1 % r == 0) gx1--; ll gy1 = y1 / r + 1, gy2 = y2 / r; if (y1 % r != 1) gy1++; if (y1 % r == 0) gy1--; if (r == 1) { gx1 = x1; gx2 = x2; gy1 = y1; gy2 = y2; } if (gx1 > gx2 || gy1 > gy2) { pair < int, pair <ll, ll> > p; ll gx = x1 / r, gy = y1 / r; if (x1 % r) gx++; if (y1 % r) gy++; bool f; if (fl == 0) { if (gx % 2) { if (gy % 2) f = 0; else f = 1; } else if (gy % 2) f = 1; else f = 0; } else { if (gx % 2) { if (gy % 2) f = 1; else f = 0; } else if (gy % 2) f = 0; else f = 1; } ll bx = 1ll * gx * r - x1 + 1; ll by = 1ll * gy * r - y1 + 1; p.F = f; p.S.F = bx; p.S.S = by; if (gx1 > gx2 && gy1 > gy2) { if (x1 + p.S.F > x2 && y1 + p.S.S > y2) { if (p.F == 0) return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1); else return 0; } if (x1 + p.S.F > x2) { ll S = 1ll * (x2 - x1 + 1) * p.S.S; if (p.F == 0) return S; else return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - S; } if (y1 + p.S.S > y2) { ll S = 1ll * (y2 - y1 + 1) * p.S.F; if (p.F == 0) return S; else return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - S; } ll v1 = 1ll * p.S.F * p.S.S + 1ll * (x2 - x1 + 1 - p.S.F) * (y2 - y1 + 1 - p.S.S); ll v2 = 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - v1; if (p.F == 0) return v1; else return v2; } if (gx1 <= gx2) { if (y1 + p.S.S <= y2) { return 1ll * solve(r, x1, y1, x2, y1 + p.S.S - 1, fl) + solve(r, x1, y1 + p.S.S, x2, y2, fl); } ll S = 0; if (p.S.F < r) S += 1ll * p.S.F * (y2 - y1 + 1); ll k = (gx2 - gx1 + 1) / 2; if (p.S.F == r) k = (gx2 - gx1 + 1 + 1) / 2; S += 1ll * (y2 - y1 + 1) * r * k; pair < int, pair <ll, ll> > p1; gx = (gx2 * r + 1) / r; gy = y1 / r; if ((gx2 * r + 1) % r) gx++; if (y1 % r) gy++; if (fl == 0) { if (gx % 2) { if (gy % 2) f = 0; else f = 1; } else if (gy % 2) f = 1; else f = 0; } else { if (gx % 2) { if (gy % 2) f = 1; else f = 0; } else if (gy % 2) f = 0; else f = 1; } bx = 1ll * gx * r - (gx2 * r + 1) + 1; by = 1ll * gy * r - y1 + 1; p1.F = f; p1.S.F = bx; p1.S.S = by; if (p1.F == p.F && gx2 * r + 1 <= x2) S += 1ll * (x2 - gx2 * r) * (y2 - y1 + 1); if (p.F == 0) return S; else return 1ll * (x2 - x1 + 1) * (y2 - y1 + 1) - S; } if (gy1 <= gy2) { if (x1 + p.S.F <= x2) { return 1ll * solve(r, x1, y1, x1 + p.S.F - 1, y2, fl) + solve(r, x1 + p.S.F, y1, x2, y2, fl); } ll S = 0; if (p.S.S < r) S += 1ll * (x2 - x1 + 1) * p.S.S; ll k = (gy2 - gy1 + 1) / 2; if (p.S.S == r) k = (gy2 - gy1 + 1 + 1) / 2; S += 1ll * (x2 - x1 + 1) * r * k; pair < int, pair <ll, ll> > p1; gx = x1 / r; gy = (gy2 * r + 1) / r; if (x1 % r) gx++; if ((gy2 * r + 1) % r) gy++; if (fl == 0) { if (gx % 2) { if (gy % 2) f = 0; else f = 1; } else if (gy % 2) f = 1; else f = 0; } else { if (gx % 2) { if (gy % 2) f = 1; else f = 0; } else if (gy % 2) f = 0; else f = 1; } bx = 1ll * gx * r - x1 + 1; by = 1ll * gy * r - (gy2 * r + 1) + 1; p1.F = f; p1.S.F = bx; p1.S.S = by; if (p1.F == p.F && gy2 * r + 1 <= y2) S += (y2 - gy2 * r) * (x2 - x1 + 1); if (p.F == 0) return S; else return (x2 - x1 + 1) * (y2 - y1 + 1) - S; } return 0; } ll stx = 1ll * gx1 * r - r + 1; ll ex = 1ll * gx2 * r; ll sty = 1ll * gy1 * r - r + 1; ll ey = 1ll * gy2 * r; ll kolx = (gx2 - gx1 + 1 + 1) / 2; ll koly = (gy2 - gy1 + 1 + 1) / 2; ll S = 1ll * kolx * koly * r * r; kolx = (gx2 - gx1 + 1) / 2; koly = (gy2 - gy1 + 1) / 2; S += 1ll * kolx * koly * r * r; pair < int, pair <ll, ll> > p; ll gx = stx / r, gy = sty / r; if (stx % r) gx++; if (sty % r) gy++; bool f; if (fl == 0) { if (gx % 2) { if (gy % 2) f = 0; else f = 1; } else if (gy % 2) f = 1; else f = 0; } else { if (gx % 2) { if (gy % 2) f = 1; else f = 0; } else if (gy % 2) f = 0; else f = 1; } ll bx = 1ll * gx * r - stx + 1; ll by = 1ll * gy * r - sty + 1; p.F = f; p.S.F = bx; p.S.S = by; ll add = solve(r, x1, y1, stx - 1, y2, fl); add += solve(r, ex + 1, y1, x2, y2, fl); add += solve(r, stx, y1, ex, sty - 1, fl); add += solve(r, stx, ey + 1, ex, y2, fl); if (p.F == 0) return S + add; else return 1ll * (ex - stx + 1) * (ey - sty + 1) - S + add; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0)); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); ll n; cin >> n >> m; for(int i = 0; i < m; i++) { cin >> l1[i] >> r1[i] >> l2[i] >> r2[i]; } a.pb(1); int d = 2; while (d * d <= n) { if (n % d == 0) { a.pb(d); a.pb(n / d); } d++; } int kopn = n; ll ans = inff; for(auto to: a) { n = kopn; ll r = to; ll S = 1ll * n * n; n /= r; ll kx = 1ll * (n + 1) / 2; ll k1 = kx * kx; kx = 1ll * n / 2; k1 += kx * kx; k1 *= r * r; ll k2 = S - k1; ll v1 = 0, v2 = 0; for(int i = 0; i < m; i++) { ll pl = 1ll * (l2[i] - l1[i] + 1) * (r2[i] - r1[i] + 1); ll c1 = solve(r, l1[i], r1[i], l2[i], r2[i], 1); ll c2 = solve(r, l1[i], r1[i], l2[i], r2[i], 0); v1 += c1; k1 -= (pl - c1); v2 += c2; k2 -= (pl - c2); } ans = min(ans, min(v1 + k1, v2 + k2)); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...