QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#421063#7785. Three Rectanglesuserqoj148WA 0ms3940kbC++145.5kb2024-05-25 10:58:442024-05-25 10:58:44

Judging History

This is the latest submission verdict.

  • [2024-05-25 10:58:44]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3940kb
  • [2024-05-25 10:58:44]
  • Submitted

answer

// xem loi giai cua nguyen viet trung nhan de minh tu code lai

#include <bits/stdc++.h>

#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int, int>
#define vpii vector<pii>
#define all(a) a.begin(), a.end()
#define sz(a) (ll) a.size()
#define fi first
#define se second
#define endl '\n'

using namespace std;

const ll mod = 1e9 + 7;
const ll md = 998244353;
const int lim = 1e5 + 1;
const int N = 2e5 + 5;
const ll inf = 1e18;
const int imx = 1e9;
const int blocksz = 500;

// Target:
// 1. Stop myself from getting too deep into a problem and move to the next one
// (This habit killed me many times)
// 2. Reach Candidate Master (287 pts left)
// 3. VOI (2025-2026)

/* Yay KMP */

ll h, w;
pair<ll, ll> ghep[4];

// Co it nhat 1 hcn nho co the bao phu toan bo hcn lon
ll solve1()
{
    sort(ghep + 1, ghep + 4);
    ll t1 = (h - ghep[1].fi + 1) * (w - ghep[1].se + 1) % mod;
    ll t2 = (h - ghep[2].fi + 1) * (w - ghep[2].se + 1) % mod;
    return t1 * t2 % mod;
}

// Co hai hcn ghep vao 2 canh chieu cao cua hcn lon
ll solve2()
{
    sort(ghep + 1, ghep + 4);
    // uu tien ghep 2 hcn lon hon (ghep[2],ghep[3])
    if (ghep[2].se + ghep[3].se < w)
        return 0;
    ll t = (h - ghep[1].fi + 1) * (w - ghep[1].se + 1) % mod;
    t *= 2;
    return t % mod;
}

// Ba hcn ghep vao cac canh chieu cao
ll solve3()
{
    ll ans = 0;
    ll nho = 0, cnt = 0; // nho nx truong hop ghep hcn thu k chung canh chieu cao vs i va j
    sort(ghep + 1, ghep + 4);
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            if (i != j)
            {
                int k = 6 - i - j;
                if (ghep[i].se + ghep[j].se >= w)
                {
                    nho += 2;
                    ans = (ans + max(0ll, (h - ghep[k].fi + 1)) * max(0ll, (w - ghep[k].se - 1)) % mod) % mod;
                }
                else
                {
                    if (ghep[i].se + ghep[j].se + ghep[k].se < w)
                        continue;
                    ll hi = min(w, ghep[j].se + ghep[k].se);
                    ll lo = max(ghep[k].se, w - ghep[i].se);
                    if (hi == w)
                        cnt++, nho++;
                    if (lo == ghep[k].se)
                        cnt++, nho++;
                    ans = (ans + hi - lo + 1) % mod;
                }
            }
    ans -= cnt;
    ans += (nho / 2);
    return ans % mod;
}

bool cmp(pair<ll, ll> x, pair<ll, ll> y)
{
    return x.se < y.se || (x.se == y.se && x.fi < y.fi);
}

ll solve4()
{
    sort(ghep + 1, ghep + 4, cmp);
    // uu tien ghep 2 hcn lon hon (ghep[2],ghep[3])
    if (ghep[2].fi + ghep[3].fi < h)
        return 0;
    ll t = (h - ghep[1].fi + 1) * (w - ghep[1].se + 1) % mod;
    t *= 2;
    return t % mod;
}

ll solve5()
{
    ll ans = 0;
    ll nho = 0;
    sort(ghep + 1, ghep + 4, cmp);
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            if (i != j)
            {
                int k = 6 - i - j;
                if (ghep[i].fi + ghep[j].fi >= h)
                {
                    nho += 2;
                    ans = (ans + (w - ghep[k].se + 1) * (h - ghep[k].fi - 1) % mod) % mod;
                }
                else
                {
                    if (ghep[i].fi + ghep[j].fi + ghep[k].fi < h)
                        continue;
                    ll hi = min(h, ghep[j].fi + ghep[k].fi);
                    ll lo = max(ghep[k].fi, h - ghep[i].fi);
                    ll cnt = 0;
                    if (hi == h)
                        cnt++, nho++;
                    if (lo == ghep[k].fi)
                        cnt++, nho++;
                    ans = (ans + hi - lo + 1) % mod;
                }
            }
    ans += (nho / 2);
    return ans % mod;
}

int chw = 0, ch = 0, cw = 0;
// th con lai
ll solve6()
{
    if (!cw && !ch)
        return 0;
    if (ch == 1)
    {
        sort(ghep + 1, ghep + 4);
        if (ghep[1].fi + ghep[2].fi >= h && min(ghep[1].se, ghep[2].se) + ghep[3].se >= w)
            return 4;
        else
            return 0;
    }
    else
    {
        if (ghep[1].se + ghep[2].se >= w && min(ghep[1].fi, ghep[2].fi) + ghep[3].fi >= h)
            return 4;
        else
            return 0;
    }
    return 0;
}

void solve()
{
    cin >> h >> w;
    chw = ch = cw = 0;
    for (int i = 1; i <= 3; i++)
    {
        cin >> ghep[i].fi >> ghep[i].se;
        chw += (ghep[i].fi == h && ghep[i].se == w);
        ch += (ghep[i].fi == h);
        cw += (ghep[i].se == w);
    }
    ll kq;
    cout << chw << " " << ch << " " << cw << endl;
    if (chw)
        kq = solve1();
    else if (ch == 2)
        kq = solve2();
    else if (ch == 3)
        kq = solve3();
    else if (cw == 2)
        kq = solve4();
    else if (cw == 3)
        kq = solve5();
    else
        kq = solve6();
    cout << kq;
}

int main()
{
    IOS;
    // freopen("input.inp", "r", stdin);
    // freopen("output.out", "w", stdout);
    // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int t;
    cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3940kb

input:

5
2 2
1 1
1 1
1 1
2 2
1 1
1 2
1 2
2 2
1 1
1 2
2 1
2 2
1 2
1 2
1 2
2 2
1 2
1 2
2 1

output:

0 0 0
0
0 0 2
8
0 1 1
4
0 0 3
6
0 1 2
4

result:

wrong answer 2nd numbers differ - expected: '8', found: '0'