QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#327587#3160. Cuttingbachbeo200720 168ms35144kbC++206.3kb2024-02-15 11:01:322024-02-15 11:01:33

Judging History

This is the latest submission verdict.

  • [2024-02-15 11:01:33]
  • Judged
  • Verdict: 20
  • Time: 168ms
  • Memory: 35144kb
  • [2024-02-15 11:01:32]
  • 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;
        if(tree[id<<1]>=1){
            tree[id<<1]=lazy[id<<1]=lazy[id];
        }
        if(tree[id<<1|1]>=1){
            tree[id<<1|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]);
            if(tree[id]>=1) 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;
    }
    void update_pos(int l,int r,int id,int p,int val){
        if(l==r){
            tree[id]=val;
            return;
        }
        pushdown(id);
        int mid=(l+r)>>1;
        if(p<=mid) update_pos(l,mid,id<<1,p,val);
        else update_pos(mid+1,r,id<<1|1,p,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,H,0};
    l[++n]={0,0,0,W};
    l[++n]={H,0,H,W};
    l[++n]={0,W,H,W};

    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);
        }
    }
    //cout << ans << '\n';
    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){
                cc[l[t].y]^=1;
                //cout << "change " << id << '\n';
                if(id>0) Segtree::update_pos(1,sy,1,l[t].y,t);
                else Segtree::update_pos(1,sy,1,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){
                //cout << '*' << t << '\n';
                Segtree::update(1,sy,1,l[t].y,l[t].v,t);
                ans+=BIT::query(l[t].v-1)-BIT::query(l[t].y)+1;
                //cout << t << ' ' << BIT::query(l[t].v-1)-BIT::query(l[t].y) << '\n';
                if(!cc[l[t].v]){
                    ans--;
                    //cout << "stupid\n";
                }
                if(!cc[l[t].y]){
                    ans--;
                    //cout << "stupid\n";
                }
            }
        }
    }
    //cout << ans << '\n';
    //cout << DSU::cnt << '\n';
    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();
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 0ms
memory: 11772kb

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:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 2ms
memory: 11880kb

input:

10 10 10
5 7 8 7
3 3 4 3
0 5 10 5
9 0 9 8
5 2 9 2
2 1 2 7
0 8 8 8
7 0 7 1
2 7 4 7
9 9 10 9

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 2ms
memory: 11824kb

input:

10 10 15
1 1 4 1
5 8 9 8
4 2 4 3
5 1 5 7
5 1 10 1
9 8 9 10
3 3 3 8
1 0 1 9
9 0 9 5
9 9 10 9
1 9 7 9
2 5 3 5
4 4 4 6
5 4 8 4
1 7 9 7

output:

4

result:

ok single line: '4'

Test #4:

score: 0
Accepted
time: 0ms
memory: 11836kb

input:

100 100 100
31 29 31 83
36 54 36 77
11 16 51 16
20 24 20 82
7 1 7 43
46 14 64 14
77 35 77 94
8 26 82 26
59 43 85 43
55 18 94 18
97 22 97 90
46 61 75 61
78 6 78 20
74 3 74 85
34 93 97 93
87 45 98 45
57 23 82 23
5 58 64 58
55 92 58 92
9 10 9 49
8 5 57 5
17 88 61 88
48 68 48 73
53 51 93 51
7 29 85 29
5...

output:

303

result:

ok single line: '303'

Test #5:

score: -5
Wrong Answer
time: 1ms
memory: 11852kb

input:

100 100 144
47 22 89 22
12 12 12 99
94 21 94 64
83 93 83 98
27 29 78 29
18 43 76 43
19 57 29 57
22 33 22 90
71 61 82 61
27 1 27 100
9 47 56 47
37 34 44 34
32 23 89 23
35 58 89 58
8 78 13 78
97 90 97 91
19 7 39 7
29 27 55 27
80 79 88 79
33 8 76 8
6 48 54 48
46 73 46 97
48 53 61 53
92 52 92 53
10 19 2...

output:

782

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 20
Accepted

Test #29:

score: 20
Accepted
time: 2ms
memory: 11988kb

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:

10525

result:

ok single line: '10525'

Test #30:

score: 0
Accepted
time: 3ms
memory: 13944kb

input:

1000 1000000000 603
601 755190731 601 810458592
934 408413681 934 991509232
677 999530155 815 999530155
168 493643722 673 493643722
471 611014716 471 737416010
297 338288031 560 338288031
359 95457712 359 618830356
526 343959777 881 343959777
925 444786130 925 668860824
514 666804490 514 983701500
6...

output:

9023

result:

ok single line: '9023'

Test #31:

score: 0
Accepted
time: 2ms
memory: 11840kb

input:

1000000000 1000 497
827959903 211 827959903 713
423671814 326 423671814 505
151915634 787 151915634 939
973586233 330 973586233 372
243989833 294 381424364 294
852825911 110 852825911 211
656054851 649 980370982 649
361463145 400 562481084 400
598057245 206 598057245 519
356401865 441 356401865 641
...

output:

6182

result:

ok single line: '6182'

Test #32:

score: 0
Accepted
time: 2ms
memory: 11940kb

input:

1000000000 1000000000 1000
630608407 74813188 630608407 572572115
428810287 713956480 539731989 713956480
640066404 189916304 777953387 189916304
139692089 138020424 436628489 138020424
232274854 245431711 232274854 706217149
76021996 254360470 90280084 254360470
78051453 144768536 78051453 46597063...

output:

7634

result:

ok single line: '7634'

Test #33:

score: 0
Accepted
time: 12ms
memory: 17408kb

input:

1000000000 1000000000 10000
669049628 139158927 669049628 226133259
718482206 453214864 721640027 453214864
922685361 202362178 922685361 269486043
176418025 189329098 176418025 207938401
924551310 799389698 971274232 799389698
913658655 45406740 913658655 115315119
684126650 488289248 684126650 538...

output:

49135

result:

ok single line: '49135'

Test #34:

score: 0
Accepted
time: 79ms
memory: 23000kb

input:

1000000000 1000000000 50000
238613172 391515513 238613172 405815949
228020608 514039210 228020608 525135195
764909506 76206052 767077509 76206052
120043781 289917261 130315212 289917261
838856354 367766371 838856354 377711111
190255664 959215979 190255664 960991962
152573495 152153917 162261418 1521...

output:

23820

result:

ok single line: '23820'

Test #35:

score: 0
Accepted
time: 156ms
memory: 34888kb

input:

1000000000 1000000000 100000
170340118 373306152 170340118 379627430
12604058 168765839 12604058 170795182
20332951 541320438 20332951 549298071
134940794 461595827 134940794 470870367
311164461 197351124 311164461 202291947
421842363 147731250 422869432 147731250
282491926 152715320 282491926 15528...

output:

9721

result:

ok single line: '9721'

Test #36:

score: 0
Accepted
time: 168ms
memory: 35144kb

input:

1000000000 1000000000 100000
648681835 61387068 648681835 61467529
482483617 633133302 490538368 633133302
238416060 954280004 238416060 960579571
971671652 48097001 971671652 52691091
961774046 226207867 961774046 234611274
143188037 361192114 152157365 361192114
631586268 619581854 639748156 61958...

output:

23400

result:

ok single line: '23400'

Test #37:

score: 0
Accepted
time: 153ms
memory: 32436kb

input:

1000000000 1000000000 100000
533066721 267929372 533066721 268068695
478609871 93625392 478609871 94238869
509029333 579208129 509709352 579208129
712522492 727418412 712719154 727418412
272180063 572902914 272180063 573774712
758504262 227729418 759289998 227729418
637434739 129362617 637434739 130...

output:

1

result:

ok single line: '1'

Test #38:

score: 0
Accepted
time: 127ms
memory: 25440kb

input:

1000000000 1000000000 100000
273576603 753501145 273576631 753501145
209049647 751024536 209049647 751024584
730324450 156458455 730324489 156458455
462842489 975962094 462842489 975962116
539789616 391587975 539789616 391588008
443086141 242291883 443086228 242291883
935928542 938420909 935928542 9...

output:

1

result:

ok single line: '1'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%