QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#421063 | #7785. Three Rectangles | userqoj148 | WA | 0ms | 3940kb | C++14 | 5.5kb | 2024-05-25 10:58:44 | 2024-05-25 10:58:44 |
Judging History
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'