QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#344973#3160. Cuttingtuanlinh1230 1ms5840kbC++201.8kb2024-03-05 21:37:252024-03-05 21:37:26

Judging History

This is the latest submission verdict.

  • [2024-03-05 21:37:26]
  • Judged
  • Verdict: 0
  • Time: 1ms
  • Memory: 5840kb
  • [2024-03-05 21:37:25]
  • Submitted

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%