QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#327566#3160. Cuttingbachbeo20070 2ms9896kbC++205.3kb2024-02-15 10:30:242024-02-15 10:30:24

Judging History

This is the latest submission verdict.

  • [2024-02-15 10:30:24]
  • Judged
  • Verdict: 0
  • Time: 2ms
  • Memory: 9896kb
  • [2024-02-15 10:30:24]
  • Submitted

answer

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=100015;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;

int sx,sy;
vector<int> cx,cy;
vector<int> qq[2*maxn];
int cc[2*maxn];

namespace DSU{
    int cnt,par[maxn];
    void init(int n){
        cnt=n;
        for(int i=1;i<=n;i++) par[i]=i;
    }
    int findpar(int u){
        if(u!=par[u]) return par[u]=findpar(par[u]);
        return u;
    }
    void unions(int u,int v){
        if(!u || !v) return;
        u=findpar(u);v=findpar(v);
        if(u==v) return;
        par[v]=u;cnt--;
    }
};
namespace BIT{
    int bit[2*maxn],sz;
    void init(int n){
        sz=n;
        for(int i=1;i<=n;i++) bit[i]=0;
    }
    void update(int x,int val){
        for(int i=x;i<=sz;i+=(i&(-i))) bit[i]+=val;
    }
    int query(int x){
        int res=0;
        for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i];
        return res;
    }
}

namespace Segtree{
    int tree[8*maxn],lazy[8*maxn];
    void pushdown(int id){
        if(!lazy[id]) return;
        tree[id<<1]=tree[id<<1|1]=lazy[id<<1]=lazy[id<<1|1]=lazy[id];
        lazy[id]=0;
    }
    void update(int l,int r,int id,int tl,int tr,int val){
        if(tr<l || r<tl) return;
        if(tl<=l && r<=tr && tree[id]!=-1){
            DSU::unions(val,tree[id]);
            tree[id]=lazy[id]=val;
            return;
        }
        pushdown(id);
        int mid=(l+r)>>1;
        update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
        int a=tree[id<<1],b=tree[id<<1|1];
        if(a>b) swap(a,b);
        if(a>0){
            if(a==b) tree[id]=a;
            else tree[id]=-1;
        }
        else if(a==0) tree[id]=b;
        else tree[id]=-1;
    }

}

int H,W,N,n;
struct line{
    int x,y,u,v;
}l[maxn];

void solve(){
    cin >> H >> W >> N;
    for(int i=1;i<=N;i++){
        int x,y,u,v;cin >> x >> y >> u >> v;
        if(x!=u || y!=v) l[++n]={x,y,u,v};
    }
    l[++n]={0,0,W,0};
    l[++n]={0,0,0,H};
    l[++n]={W,0,W,H};
    l[++n]={0,H,W,H};

    for(int i=1;i<=n;i++){
        cx.push_back(l[i].x);
        cx.push_back(l[i].u+1);
        cy.push_back(l[i].y);
        cy.push_back(l[i].v+1);
    }
    sort(cx.begin(),cx.end());
    sort(cy.begin(),cy.end());
    cx.erase(unique(cx.begin(),cx.end()),cx.end());
    cy.erase(unique(cy.begin(),cy.end()),cy.end());
    sx=(int)cx.size()-1;sy=(int)cy.size()-1;

    int ans=0;
    for(int i=1;i<=n;i++){
        l[i].x=lower_bound(cx.begin(),cx.end(),l[i].x)-cx.begin()+1;
        l[i].u=lower_bound(cx.begin(),cx.end(),l[i].u+1)-cx.begin();
        l[i].y=lower_bound(cy.begin(),cy.end(),l[i].y)-cy.begin()+1;
        l[i].v=lower_bound(cy.begin(),cy.end(),l[i].v+1)-cy.begin();

        if(l[i].x==l[i].u) qq[l[i].x].push_back(i);
        else{
            ans--;
            //cout << '*' << i << '\n';
            qq[l[i].x].push_back(i);
            qq[l[i].u+1].push_back(-i);
        }
    }
    DSU::init(n);
    BIT::init(sy);
    for(int i=1;i<=sx;i++){
        for(int id:qq[i]){
            int t=abs(id);
            if(l[t].x==l[t].u) Segtree::update(1,sy,1,l[t].y,l[t].v,t);
            else{
                cc[l[t].y]^=1;
                if(id>0) Segtree::update(1,sy,1,l[t].y,l[t].y,t);
                else Segtree::update(1,sy,1,l[t].y,l[t].y,0);
                BIT::update(l[t].y,(id<0?-1:1));
            }
        }
        for(int id:qq[i]){
            int t=abs(id);
            if(l[t].x==l[t].u){
                ans+=BIT::query(l[t].v-1)-BIT::query(l[t].y)+1;
                if(!cc[l[t].v]) ans--;
                if(!cc[l[t].y]) ans--;
            }
        }
    }
    ans+=DSU::cnt;
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: 2ms
memory: 9896kb

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%