QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#344973 | #3160. Cutting | tuanlinh123 | 0 | 1ms | 5840kb | C++20 | 1.8kb | 2024-03-05 21:37:25 | 2024-03-05 21:37:26 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
const ll maxn=100005;
ll a[maxn], b[maxn], c[maxn], d[maxn];
map <ll, vector <pair<ll, pll>>> Mp;
map <ll, ll> bit;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll w, h, n, e=0, v=0; cin >> w >> h >> n;
for (ll i=1; i<=n+4; i++)
{
if (i<=n) cin >> a[i] >> b[i] >> c[i] >> d[i];
if (i==n+1) a[i]=0, b[i]=0, c[i]=w, d[i]=0;
if (i==n+2) a[i]=0, b[i]=0, c[i]=0, d[i]=h;
if (i==n+3) a[i]=0, b[i]=h, c[i]=w, d[i]=h;
if (i==n+4) a[i]=w, b[i]=0, c[i]=w, d[i]=h;
if (a[i]==c[i])
{
e+=d[i]-b[i], v+=d[i]-b[i]+1;
Mp[b[i]-1].pb({1, {1, a[i]}});
Mp[d[i]].pb({1, {-1, a[i]}});
if (i<=n) assert(a[i]>0 && a[i]<w);
}
else
{
e+=c[i]-a[i], v+=c[i]-a[i]+1;
Mp[b[i]].pb({2, {a[i], c[i]}});
if (i<=n) assert(b[i]>0 && b[i]<h);
}
}
auto update=[&](ll l, ll r)
{
l++, r++;
for (; l<=w+1; l+=l&(-l)) bit[l]++;
for (++r; r<=w+1; r+=r&(-r)) bit[r]--;
};
auto query=[&](ll i)
{
ll ans=0;
for (++i; i; i-=i&(-i)) ans+=bit[i];
return ans;
};
for (pair<ll, vector <pair<ll, pll>>> i:Mp)
{
vector <pair<ll, pll>> event=i.se;
sort(event.begin(), event.end(), greater<pair<ll, pll>>());
for (pair<ll, pll> e:event)
{
if (e.fi==2) update(e.se.fi, e.se.se);
else v+=e.se.fi*query(e.se.se);
}
}
cout << e-v+1 << "\n";
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5840kb
input:
10 10 10 6 5 6 10 4 0 4 3 3 2 3 10 0 8 2 8 3 8 5 8 0 2 7 2 9 6 9 8 8 2 8 7 5 3 6 3 1 1 7 1
output:
0
result:
wrong answer 1st lines differ - expected: '3', found: '0'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #29:
score: 0
Wrong Answer
time: 1ms
memory: 3976kb
input:
1000 1000 600 467 160 467 845 10 68 10 101 358 513 358 621 66 671 620 671 351 549 596 549 87 746 87 917 526 145 526 559 118 314 118 868 87 584 373 584 4 117 4 150 801 265 801 416 417 269 417 630 480 144 480 550 945 203 945 768 679 484 679 525 93 342 93 504 954 176 954 270 453 206 453 565 898 668 898...
output:
10512
result:
wrong answer 1st lines differ - expected: '10525', found: '10512'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%