QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372179#3007. Intersecting RectanglesInfinityNSAC ✓150ms12208kbC++202.4kb2024-03-31 02:36:472024-03-31 02:36:49

Judging History

你现在查看的是最新测评结果

  • [2024-03-31 02:36:49]
  • 评测
  • 测评结果:AC
  • 用时:150ms
  • 内存:12208kb
  • [2024-03-31 02:36:47]
  • 提交

answer

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


const int maxn=3e5+10;

int n;
vector<int>cand;
vector<pair<pii,pii>>events;

int getuj(int x){
    ///return x;
    int ret=lower_bound(cand.begin(),cand.end(),x)-cand.begin();
    ///printf("%d %d DD\n",x,ret);
    return ret;
}

int tree[maxn*4];
void update(int x,int l,int r,int id,int val){
    if(l==r){
        tree[x]+=val;
        return;
    }
    int mid=(l+r)/2;
    if(id<=mid)update(x*2,l,mid,id,val);
    else update(x*2+1,mid+1,r,id,val);
    tree[x]=tree[x*2]+tree[x*2+1];
}
int qry(int x,int l,int r,int lp,int rp){
    if(l>rp || r<lp)return 0;
    if(l>=lp && r<=rp)return tree[x];
    int mid=(l+r)/2;
    return qry(x*2,l,mid,lp,rp)+qry(x*2+1,mid+1,r,lp,rp);
}

int main(){

    ///freopen("test.txt","r",stdin);

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x1,x2,y1,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        cand.pb(x1);cand.pb(x2);cand.pb(y1);cand.pb(y2);
        events.pb({{x1,1},{y1,y2} });
        events.pb({{x2,-1},{y1,y2} });
    }
    sort(cand.begin(),cand.end());
    cand.resize(unique(cand.begin(),cand.end())-cand.begin());
    //for(int i=0;i<cand.size();i++)printf("%d %d | ",cand[i],i);
    //printf(" CAND\n");
    for(int i=0;i<events.size();i++){
        events[i].ff.ff=getuj(events[i].ff.ff);
        events[i].ss.ff=getuj(events[i].ss.ff);
        events[i].ss.ss=getuj(events[i].ss.ss);
    }

    sort(events.begin(),events.end());

    int rez=0;
    for(int i=0;i<events.size();i++){

        int l,r;
        l=events[i].ss.ff;
        r=events[i].ss.ss;

        rez=max(rez,qry(1,0,cand.size()-1,l+1,r-1));

        ///printf("%d %d | %d | %d\n",l,r,events[i].ff.ff,rez);

        update(1,0,cand.size()-1,l,events[i].ff.ss);
        update(1,0,cand.size()-1,r,events[i].ff.ss);

    }

    printf("%d\n",min(rez,1));

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 150ms
memory: 10808kb

input:

100000
-1000000 -1000000 -990000 -990000
-989500 -999999 -979500 -989999
-979000 -999998 -969000 -989998
-968500 -999997 -958500 -989997
-958000 -999996 -948000 -989996
-947500 -999995 -937500 -989995
-937000 -999994 -927000 -989994
-926500 -999993 -916500 -989993
-916000 -999992 -906000 -989992
-90...

output:

0

result:

ok answer is 0

Test #2:

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

input:

1
-1000000000 -1000000000 1000000000 1000000000

output:

0

result:

ok answer is 0

Test #3:

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

input:

13
7516209 7550707 89875156 98173013
47476247 5897894 76370217 37077815
8554547 13903693 70271199 58517091
59377179 10691227 85248839 74526588
25381296 75287750 63190532 94490939
1744167 1968914 33149094 90583877
3729241 63828859 70195565 67888762
23931088 47849774 35764715 67174851
82068785 3054639...

output:

1

result:

ok answer is 1

Test #4:

score: 0
Accepted
time: 83ms
memory: 12064kb

input:

100000
-10000000 -10000000 -9999802 -9999804
-9999800 -9999800 -9999602 -9999604
-9999600 -9999600 -9999402 -9999404
-9999400 -9999400 -9999202 -9999204
-9999200 -9999200 -9999002 -9999004
-9999000 -9999000 -9998802 -9998804
-9998800 -9998800 -9998602 -9998604
-9998600 -9998600 -9998402 -9998404
-99...

output:

0

result:

ok answer is 0

Test #5:

score: 0
Accepted
time: 138ms
memory: 12208kb

input:

100000
3035800 3035800 3035998 3035996
-1397800 -1397800 -1397602 -1397604
9002800 9002800 9002998 9002996
-3410800 -3410800 -3410602 -3410604
2188200 2188200 2188398 2188396
-7752600 -7752600 -7752402 -7752404
819600 819600 819798 819796
-4035400 -4035400 -4035202 -4035204
658800 658800 658998 6589...

output:

1

result:

ok answer is 1

Test #6:

score: 0
Accepted
time: 125ms
memory: 10888kb

input:

100000
-500000000 -300000000 400000000 290000000
-499999000 -299999000 399999100 289999100
-499998000 -299998000 399998200 289998200
-499997000 -299997000 399997300 289997300
-499996000 -299996000 399996400 289996400
-499995000 -299995000 399995500 289995500
-499994000 -299994000 399994600 289994600...

output:

0

result:

ok answer is 0

Test #7:

score: 0
Accepted
time: 117ms
memory: 10412kb

input:

100000
-500000000 -300000000 400000000 290000000
-499999000 -299999000 400000010 290000020
-499998000 -299998000 400000020 290000040
-499997000 -299997000 400000030 290000060
-499996000 -299996000 400000040 290000080
-499995000 -299995000 400000050 290000100
-499994000 -299994000 400000060 290000120...

output:

1

result:

ok answer is 1

Test #8:

score: 0
Accepted
time: 1ms
memory: 3888kb

input:

15
0 0 1000 1000
70 70 875 875
2 2 995 995
6 6 980 980
20 20 930 950
40 40 890 910
200 200 700 700
360 390 680 680
430 400 650 600
490 495 520 505
-1000 -1000 -800 -800
-2000 -2000 -1700 -1800
-400 -400 -200 -250
-125 -140 -95 -95
-3 -3 -1 -1

output:

0

result:

ok answer is 0

Test #9:

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

input:

16
0 0 1000 1000
70 70 875 875
2 2 995 995
6 6 980 980
20 20 930 950
40 40 890 910
65 69 905 920
200 200 700 700
360 390 680 680
430 400 650 600
490 495 520 505
-1000 -1000 -800 -800
-2000 -2000 -1700 -1800
-400 -400 -200 -250
-125 -140 -95 -95
-3 -3 -1 -1

output:

1

result:

ok answer is 1

Test #10:

score: 0
Accepted
time: 97ms
memory: 12120kb

input:

99900
-5000000 3000000 -4999992 3000011
-4999985 2999985 -4999977 2999996
-4999970 2999970 -4999962 2999981
-4999955 2999955 -4999947 2999966
-4999940 2999940 -4999932 2999951
-4999925 2999925 -4999917 2999936
-4999910 2999910 -4999902 2999921
-4999895 2999895 -4999887 2999906
-4999880 2999880 -4999...

output:

0

result:

ok answer is 0

Test #11:

score: 0
Accepted
time: 110ms
memory: 10164kb

input:

99901
-5000000 3000000 -4999992 3000011
-4999985 2999985 -4999977 2999996
-4999970 2999970 -4999962 2999981
-4999955 2999955 -4999947 2999966
-4999940 2999940 -4999932 2999951
-4999925 2999925 -4999917 2999936
-4999910 2999910 -4999902 2999921
-4999895 2999895 -4999887 2999906
-4999880 2999880 -4999...

output:

1

result:

ok answer is 1

Test #12:

score: 0
Accepted
time: 101ms
memory: 10208kb

input:

99901
-5000000 3000000 -4999992 3000011
-4999985 2999985 -4999977 2999996
-4999970 2999970 -4999962 2999981
-4999955 2999955 -4999947 2999966
-4999940 2999940 -4999932 2999951
-4999925 2999925 -4999917 2999936
-4999910 2999910 -4999902 2999921
-4999895 2999895 -4999887 2999906
-4999880 2999880 -4999...

output:

1

result:

ok answer is 1

Test #13:

score: 0
Accepted
time: 92ms
memory: 10388kb

input:

99900
-5000000 3000000 -4999993 3000008
-4999985 2999997 -4999978 3000005
-4999970 2999994 -4999963 3000002
-4999955 2999991 -4999948 2999999
-4999940 2999988 -4999933 2999996
-4999925 2999985 -4999918 2999993
-4999910 2999982 -4999903 2999990
-4999895 2999979 -4999888 2999987
-4999880 2999976 -4999...

output:

0

result:

ok answer is 0

Test #14:

score: 0
Accepted
time: 110ms
memory: 10468kb

input:

99901
-3501529 2700307 -3501000 2700358
-5000000 3000000 -4999993 3000008
-4999985 2999997 -4999978 3000005
-4999970 2999994 -4999963 3000002
-4999955 2999991 -4999948 2999999
-4999940 2999988 -4999933 2999996
-4999925 2999985 -4999918 2999993
-4999910 2999982 -4999903 2999990
-4999895 2999979 -4999...

output:

1

result:

ok answer is 1

Test #15:

score: 0
Accepted
time: 140ms
memory: 10204kb

input:

99901
-4973405 2994681 -4973398 2994689
-4271765 2854353 -4271758 2854361
-4245155 2849031 -4245148 2849039
-4380800 2876160 -4380793 2876168
-3842675 2768535 -3842668 2768543
-4732460 2946492 -4732453 2946500
-3998420 2799684 -3998413 2799692
-3678485 2735697 -3678478 2735705
-4751105 2950221 -4751...

output:

1

result:

ok answer is 1

Test #16:

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

input:

11
1 1 10 6
3 19 8 24
13 4 18 9
22 7 30 13
35 3 41 8
32 11 37 18
28 35 38 41
4 5 40 20
34 17 42 28
39 16 43 25
20 26 25 31

output:

1

result:

ok answer is 1

Test #17:

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

input:

9
1 1 10 6
3 19 8 24
13 4 18 9
22 7 30 13
35 3 41 8
32 11 37 18
28 35 38 41
39 16 43 25
20 26 25 31

output:

0

result:

ok answer is 0

Test #18:

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

input:

10
1 1 10 6
3 19 8 24
13 4 18 9
22 7 30 13
35 3 41 8
32 11 37 18
28 35 38 41
39 16 43 25
20 26 25 31
11 5 51 21

output:

1

result:

ok answer is 1

Test #19:

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

input:

8
20 -105 40 -90
30 -70 50 -50
60 -140 80 -20
-10 -10 10 10
100 -130 120 -110
90 -100 140 -80
110 -40 130 -30
150 -150 190 -120

output:

0

result:

ok answer is 0

Test #20:

score: 0
Accepted
time: 1ms
memory: 3928kb

input:

9
20 -105 40 -90
30 -70 50 -50
60 -140 80 -20
-10 -10 10 10
100 -130 120 -110
15 -95 155 -45
90 -100 140 -80
110 -40 130 -30
150 -150 190 -120

output:

1

result:

ok answer is 1

Test #21:

score: 0
Accepted
time: 145ms
memory: 10596kb

input:

99600
-77794400 19794400 -77793650 19795225
1396500 -2520250 1396545 -2520188
28060080 150449752 28060137 150449814
346350 -945025 346395 -944963
-110922500 -200399375 -110922043 -200398752
-81789600 23789600 -81788850 23790425
-114069800 -202759850 -114069343 -202759227
29941570 151853633 29941627 ...

output:

0

result:

ok answer is 0

Test #22:

score: 0
Accepted
time: 140ms
memory: 10584kb

input:

99601
-129837500 -214585625 -129837043 -214585002
1151250 -2152375 1151295 -2152313
839300 -1684450 839345 -1684388
809550 -1639825 809595 -1639763
28608550 150858995 28608607 150859057
697500 -1471750 697545 -1471688
-83810300 25810300 -83809550 25811125
28976710 151133699 28976767 151133761
-12075...

output:

1

result:

ok answer is 1

Test #23:

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

input:

2
1 1 4 4
0 2 3 5

output:

1

result:

ok answer is 1

Test #24:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

2
1 1 4 3
0 0 3 4

output:

1

result:

ok answer is 1