oj.uz

Submission #155212

# Submission time Handle Problem Language Result Execution time Memory
155212 2019-09-27T06:44:42 Z Dasha_Gnedko Chessboard (IZhO18_chessboard) C++14
8 / 100
 58 ms 5240 KB 
#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 = 1e6 + 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;

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

int l1[N], r1[N], l2[N], r2[N];
int m;

pair <int, pair <int, int> > get(int r, int x, int y, int fl)
{
    int gx = x / r + 1, gy = y / r + 1;

    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;
    }

    int bx = gx * r - gx + 1;
    int by = gy * r - gy + 1;

    return {f, {bx, by}};

}

int solve(int r, int x1, int y1, int x2, int y2, int fl)
{
    int gx1 = x1 / r + 1, gx2 = x2 / r;
    if (gx1 % r != 1) gx1++;

    int gy1 = y1 / r + 1, gy2 = y2 / r;
    if (gy1 % r != 1) gy1++;

    if (r == 1)
    {
        gx1 = x1; gx2 = x2; gy1 = y1; gy2 = y2;
    }

    if (gx1 > gx2 || gy1 > gy2)
    {
        return 0;
    }

    int stx = gx1 * r - r + 1;
    int ex = gx2 * r;

    int sty = gy1 * r - r + 1;
    int ey = gy2 * r;

    int kolx = (gx2 - gx1 + 1 + 1) / 2;
    int koly = (gy2 - gy1 + 1 + 1) / 2;

    int S = kolx * koly * r * r;

    kolx = (gx2 - gx1 + 1) / 2;
    koly = (gy2 - gy1 + 1) / 2;

    S += kolx * koly * r * r;

    pair < int, pair <int, int> > p = get(r, stx, sty, fl);

//    cout << p.F << " " << S << endl;

    if (p.F == 0) return S;
    else return (ex - stx + 1) * (ey - sty + 1) - S;

}

int get_ans(int r, int n)
{
    int S = n * n;

    int kx = (n + 1) / 2;
    int k1 = kx * kx;
    kx = n / 2;
    k1 += kx * kx;
    k1 *= r * r;

    int k2 = S - k1;

    int v1 = 0, v2 = 0;

    for(int i = 0; i < m; i++)
    {
        int pl = (l2[i] - l1[i] + 1) * (r2[i] - r1[i] + 1);
        int c1 = solve(r, l1[i], r1[i], l2[i], r2[i], 1);
        int c2 = solve(r, l1[i], r1[i], l2[i], r2[i], 0);
        v1 += c1;
        k1 -= (pl - c1);

        v2 += c2;
        k2 -= (pl - c2);
    }

    return min(v1 + k1, v2 + k2);

}

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);

    int n;
    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        cin >> l1[i] >> r1[i] >> l2[i] >> r2[i];
//        cout << solve(1, l1[i], r1[i], l2[i], r2[i], 1) << endl;
    }

    cout << get_ans(1, n);

}

Subtask #1
0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3960 KB Output is correct
2 Correct 12 ms 1208 KB Output is correct
3 Correct 26 ms 2680 KB Output is correct
4 Correct 29 ms 2680 KB Output is correct
5 Correct 36 ms 3320 KB Output is correct
6 Correct 23 ms 2316 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 23 ms 2296 KB Output is correct
9 Correct 58 ms 5240 KB Output is correct
10 Correct 33 ms 3064 KB Output is correct

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 41 ms 3960 KB Output is correct
2 Correct 12 ms 1208 KB Output is correct
3 Correct 26 ms 2680 KB Output is correct
4 Correct 29 ms 2680 KB Output is correct
5 Correct 36 ms 3320 KB Output is correct
6 Correct 23 ms 2316 KB Output is correct
7 Correct 7 ms 760 KB Output is correct
8 Correct 23 ms 2296 KB Output is correct
9 Correct 58 ms 5240 KB Output is correct
10 Correct 33 ms 3064 KB Output is correct
11 Incorrect 2 ms 376 KB Output isn't correct
12 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 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -