QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#345150#3160. Cuttingtuanlinh1230 1ms3716kbC++204.6kb2024-03-06 11:13:232024-03-06 11:13:23

Judging History

This is the latest submission verdict.

  • [2024-03-06 11:13:23]
  • Judged
  • Verdict: 0
  • Time: 1ms
  • Memory: 3716kb
  • [2024-03-06 11:13:23]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll int
#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];

namespace BIT
{
    ll n;
    vector <ll> bit;
    void init(ll sz) {n=sz, bit.assign(n+1, 0);}

    void update(ll l, ll r)
    {
        for (; l<=n; l+=l&(-l)) bit[l]++;
        for (++r; r<=n; r+=r&(-r)) bit[r]--;
    }

    ll query(ll i)
    {
        ll ans=0;
        for (; i; i-=i&(-i)) ans+=bit[i];
        return ans;
    }
};

namespace DSU
{
    ll n;
    vector <ll> pa, Rank;
    void init(ll sz) 
    {
        n=sz, Rank.assign(n+1, 0);
        pa.resize(n+1), iota(pa.begin(), pa.end(), 0);
    }

    ll Find(ll i)
    {
        if (pa[i]!=i) pa[i]=Find(pa[i]);
        return pa[i];
    }

    void Union(ll a, ll b)
    {
        a=Find(a), b=Find(b);
        if (a==b) return;
        if (Rank[a]<Rank[b]) swap(a, b);
        if (Rank[a]==Rank[b]) Rank[a]++;
        pa[b]=a;
    }
};

namespace SegTree
{
    ll n;
    vector <ll> St, lz;
    void init(ll sz) {n=sz, St.assign(n*4+1, 0), lz.assign(n*4+1, 0);}

    ll Merge(ll a, ll b)
    {
        if (a==-1 || b==-1 || (a>0 && b>0)) return -1;
        return a+b;
    }

    void Move(ll i)
    {
        if (!lz[i]) return;
        ll t=lz[i]; lz[i]=0;
        St[i*2]=St[i*2+1]=lz[i*2]=lz[i*2+1]=t;
    }

    void update_ver(ll i, ll Start, ll End, ll idx, ll val)
    {
        if (Start>idx || End<idx) return;
        if (Start==End) {St[i]=val; return;}
        ll mid=(Start+End)/2;
        if (idx<=mid) update_ver(i*2, Start, mid, idx, val);
        else update_ver(i*2+1, mid+1, End, idx, val);
        St[i]=Merge(St[i*2], St[i*2+1]);
    }
    void update_ver(ll idx, ll val) {update_ver(1, 1, n, idx, val);}

    void update_hor(ll i, ll Start, ll End, ll l, ll r, ll val)
    {
        if (Start>r || End<l) return;
        if (l<=Start && End<=r && St[i]!=-1)
        {
            if (St[i]) DSU::Union(val, St[i]), St[i]=lz[i]=val;
            return;
        }
        ll mid=(Start+End)/2;
        if (mid>=l) update_hor(i*2, Start, mid, l, r, val);
        if (mid+1<=r) update_hor(i*2+1, mid+1, End, l, r, val);
        St[i]=Merge(St[i*2], St[i*2+1]);
    }
    void update_hor(ll l, ll r, ll val) {update_hor(1, 1, n, l, r, val);}
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll w, h, n; cin >> w >> h >> n; n+=4;
    long long e=0, v=0;
    vector <ll> cx, cy;
    for (ll i=1; i<=n; i++)
    {
        if (i<=n-4) cin >> a[i] >> b[i] >> c[i] >> d[i];
        if (i==n-3) 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-1) a[i]=0, b[i]=h, c[i]=w, d[i]=h;
        if (i==n) a[i]=w, b[i]=0, c[i]=w, d[i]=h;
        cx.pb(a[i]), cx.pb(c[i]), cy.pb(b[i]), cy.pb(d[i]);
        if (a[i]==c[i]) e+=d[i]-b[i], v+=d[i]-b[i]+1;
        else e+=c[i]-a[i], v+=c[i]-a[i]+1;
    }
    sort(cx.begin(), cx.end());
    cx.resize(unique(cx.begin(), cx.end())-cx.begin());
    sort(cy.begin(), cy.end());
    cy.resize(unique(cy.begin(), cy.end())-cy.begin());
    ll kx=cx.size(), ky=cy.size();
    DSU::init(n), SegTree::init(kx), BIT::init(kx);
    vector <vector <pll>> event(ky+2);
    for (ll i=1; i<=n; i++)
    {
        a[i]=lower_bound(cx.begin(), cx.end(), a[i])-cx.begin()+1;
        b[i]=lower_bound(cy.begin(), cy.end(), b[i])-cy.begin()+1;
        c[i]=lower_bound(cx.begin(), cx.end(), c[i])-cx.begin()+1;
        d[i]=lower_bound(cy.begin(), cy.end(), d[i])-cy.begin()+1;
        if (a[i]==c[i]) event[b[i]].pb({0, i}), event[d[i]+1].pb({0, -i});
        else event[b[i]].pb({1, i});
    }
    for (ll i=1; i<=ky+1; i++)
    {
        sort(event[i].begin(), event[i].end());
        for (pll j:event[i])
        {
            if (!j.fi)
            {
                if (j.se>0)
                {
                    SegTree::update_ver(a[j.se], j.se);
                    v+=BIT::query(a[j.se]);
                }
                else
                {
                    SegTree::update_ver(a[-j.se], 0);
                    v-=BIT::query(a[-j.se]);
                }
            }
            else
            {
                SegTree::update_hor(a[j.se], c[j.se], j.se);
                BIT::update(a[j.se], c[j.se]);
            }
        }
    }
    for (ll i=1; i<=n; i++)
        if (DSU::pa[i]<0) e++;
    cout << e-v << "\n";
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3664kb

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:

-1

result:

wrong answer 1st lines differ - expected: '3', found: '-1'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #29:

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

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:

10511

result:

wrong answer 1st lines differ - expected: '10525', found: '10511'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%