oj.uz

Submission #155168

# Submission time Handle Problem Language Result Execution time Memory
155168 2019-09-26T18:25:12 Z srvlt Chessboard (IZhO18_chessboard) C++14
8 / 100
 40 ms 1784 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse2,avx")
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
//#define int long long
using namespace std;

void dout() {
    cerr << endl;
}

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 3;
const ll inf = 1e18;

int k, p[2][N], rx[N], ry[N], rx2[N], ry2[N];
ll n, ans = inf, A, Z, S, W, sq_A;

int color(int x, int y) {
    return ((x - 1) / A + (y - 1) / A + Z) & 1;
}

int num(int x) {
    return (x - 1) / A & 1;
}

ll getL() {
    int x = n / A;
    int x1 = ((x + 1) >> 1), x2 = (x >> 1);
    ll res = sq_A * ((ll)x1 * x1 + x2 * x2);
    if (Z == 0) {
        return res;
    }   else {
        return n * n - res;
    }
}

ll getval(int l, int r, int a, int b) {
    ll res1 = 0;
    if (l >= 1) {
        int q = (l - 1) / A;
        int last = q * A + 1;
        if (num(last) == 0) {
            res1 += (l - last + 1) * a;
        }   else {
            res1 += (l - last + 1) * b;
        }
        res1 += (((q + 1) >> 1) * a + (q >> 1) * b) * A;
    }
    ll res2 = 0;
    if (l >= 1) {
        int q = (r - 1) / A;
        int last = q * A + 1;
        if (num(last) == 0) {
            res2 += (r - last + 1) * a;
        }   else {
            res2 += (r - last + 1) * b;
        }
        res2 += (((q + 1) >> 1) * a + (q >> 1) * b) * A;
    }
    return res2 - res1;
}

ll getans() {
    for (int i = 1; i <= n; i++) {
        p[0][i] = p[0][i - 1];
        p[1][i] = p[1][i - 1];
        if (color(i, 1)) {
            p[0][i]++;
        }   else {
            p[1][i]++;
        }
    }
    ll res = 0;
    for (int i = 0; i < k; i++) {
        int v1 = p[0][rx2[i]] - p[0][rx[i] - 1];
        int v2 = p[1][rx2[i]] - p[1][rx[i] - 1];
        res += getval(ry[i] - 1, ry2[i], v1, v2);
    }
    return res;
}

void solve(int tc) {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        cin >> rx[i] >> ry[i] >> rx2[i] >> ry2[i];
        S += (ll)(rx2[i] - rx[i] + 1) * (ry2[i] - ry[i] + 1);
    }
    vector <int> factors = {};
    for (int i = 1; i < n; i++) {
        if (n % i == 0) {
            factors.pb(i);
        }
    }
    for (auto i : factors) {
        A = i;
        sq_A = A * A;
        for (int j = 0; j < 2; j++) {
            Z = j;
            W = getans();
            ans = min(ans, W + W + getL() - S);
        }
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1784 KB Output is correct
2 Incorrect 12 ms 764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1784 KB Output is correct
2 Incorrect 12 ms 764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 40 ms 1784 KB Output is correct
10 Incorrect 12 ms 764 KB Output isn't correct
11 Halted 0 ms 0 KB -