oj.uz

Submission #521851

# Submission time Handle Problem Language Result Execution time Memory
521851 2022-02-03T10:09:32 Z vonatlus Chessboard (IZhO18_chessboard) C++17
8 / 100
 26 ms 1088 KB 
/// adil sultanov | vonat1us 

#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
 
using namespace std;

using ll = long long;
using pii = pair<int, int>;                                   

const int MOD = 1e9 + 7; 
const int INF = 1e9 + 1e2;
  
void fin() {
#ifdef AM
    freopen(".in", "r", stdin);
#endif        
}                   

const bool flag = 0;

const int N = 1e5+10;

void ma1n() {
    ll n, k;
    cin >> n >> k;
    vector<int> v;
    for (int i = 1; i <= sqrt(n); ++i) {
        if (n%i == 0) {
            v.pb(i);
            if (i*i != n) {
                v.pb(n/i);
            }
        }
    }
    sort(all(v));
    v.pop_back();
    vector<ll> res1(sz(v)), res2(sz(v));
    for (int i = 0; i < sz(v); ++i) {
        ll d = v[i];
        ll cnt = n/d;
        ll cnt1 = cnt/2;
        ll cnt2 = (cnt+1)/2;
        res1[i] = cnt1*cnt2*d*d*2;
        res2[i] = n*n - res1[i];
    }
    
    auto get = [&](int x, int y, int d) {
        if (x < 0 || y < 0) return 0ll;
        bool color = ((x/d)%2 != (y/d)%2); 
        int cx = (x+1)%d;
        if (cx == 0) cx = d;
        int cy = (y+1)%d;
        if (cy == 0) cy = d;
        ll res = 0;
        ll cur = (x/d)/2*d*cy;
        if (!color && (x/d)&1) {
            cur += d*cy;
        } 
        res += cur;
        if (color) { // black
            res += cx*cy;
        } 
        cur = (y/d)/2*d*cx;
        if (!color && (y/d)&1) {
            cur += d*cx;
        }
        res += cur;
        x = (x/d-1)*d+d-1;
        y = (y/d-1)*d+d-1;
        res += ((((x+1)/d)*((y+1)/d))/2)*d; 
        return res;
    };

    //cout << get(2, 2, 1) << " " << get(2, 1, 1) << " " << get(1, 2, 1) << " " << get(1, 1, 1) << "\n";
   // cout << get(2, 3, 2) << " " << get(2, 2, 2) << " " << get(1, 3, 2) << " " << get(1, 2, 2) << "\n";
    //return;

    while (k--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--, c--, d--;    
        for (int t = 0; t < sz(v); ++t) {
            int dv = v[t];
            ll sum = get(c, d, dv) - get(c, b-1, dv) - get(a-1, d, dv) + get(a-1, b-1, dv);
            ll inv = (c-a+1)*1ll*(d-b+1) - sum;
            //cout << "D: " << dv << ", " << a << " " << b << " " << c << " " << d << " | " << sum << " " << inv << "\n";
            res1[t] -= sum;
            res1[t] += inv;
            res2[t] -= inv;
            res2[t] += sum;
        }
    }
    ll ans = n*n;
    for (int i = 0; i < sz(v); ++i) {
        ans = min({ans, res1[i], res2[i]});    
    }
    cout << ans;
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), fin();
    int ts = 1;
    if (flag) {
        cin >> ts;
    }
    while (ts--) {
        ma1n(); 
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 26 ms 1088 KB Output isn't correct
10 Halted 0 ms 0 KB -