QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#770844#8775. MountainCraftocharin#RE 260ms172400kbC++202.7kb2024-11-22 00:46:092024-11-22 00:46:10

Judging History

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

  • [2024-11-22 00:46:10]
  • 评测
  • 测评结果:RE
  • 用时:260ms
  • 内存:172400kb
  • [2024-11-22 00:46:09]
  • 提交

answer

/*

                                _/                                      _/
       _/_/        _/_/_/      _/_/_/        _/_/_/      _/  _/_/               _/_/_/
    _/    _/    _/            _/    _/    _/    _/      _/_/          _/       _/    _/
   _/    _/    _/            _/    _/    _/    _/      _/            _/       _/    _/
    _/_/        _/_/_/      _/    _/      _/_/_/      _/            _/       _/    _/

*/
#include<bits/stdc++.h>
#define int long long

using namespace std;
const long double s2=sqrtl(2);
const int N=1e6+8;
int cnt=1;
struct tree{
    int l,r,mi,sum,tag;
    tree():l(0),r(0),mi(0),sum(0),tag(0){};
};
vector<tree>s(N<<2);
struct SegmentTree{
    void pushtag(int &u,int cl,int cr,int k){
        if(!u){
            u=++cnt;
            s[u].sum=cr-cl+1;
        }
        s[u].mi+=k;
        s[u].tag+=k;
    }
    void pushdown(int u,int cl,int cr){
        int mid=cl+cr>>1;
        pushtag(s[u].l,cl,mid,s[u].tag);
        pushtag(s[u].r,mid+1,cr,s[u].tag);
        s[u].tag=0;
    }
    void pushup(int u,int cl,int cr){
        s[u].mi=min(s[s[u].l].mi,s[s[u].r].mi);
        s[u].sum=0;
        int mid=cl+cr>>1;
        if(s[u].l){
            if(s[s[u].l].mi==s[u].mi) s[u].sum+=s[s[u].l].sum;
        }
        else s[u].sum+=mid-cl+1;
        if(s[u].r){
            if(s[s[u].r].mi==s[u].mi) s[u].sum+=s[s[u].r].sum;
        }
        else s[u].sum+=cr-mid;
    }
    int modify(int u,int cl,int cr,int l,int r,int k){
        if(!u) u=++cnt,s[u].sum=cr-cl+1;
        if(l<=cl && cr<=r){
            pushtag(u,cl,cr,k);
            return u;
        }
        pushdown(u,cl,cr);
        int mid=cl+cr>>1;
        if(l<=mid) s[u].l=modify(s[u].l,cl,mid,l,r,k);
        if(mid<r) s[u].r=modify(s[u].r,mid+1,cr,l,r,k);
        pushup(u,cl,cr);
        return u;
    }
    int query(int u,int cl,int cr){
        if(s[1].mi==0) return cr-cl+1-s[1].sum;
        else return cr-cl+1;
    }
}seg;

void dfs(int u,int cl,int cr){
    if(!u) return;
    cerr<<u<<" "<<cl<<" "<<cr<<" : "<<s[u].mi<<" "<<s[u].sum<<endl;
    int mid=cl+cr>>1;
    dfs(s[u].l,cl,mid);
    dfs(s[u].r,mid+1,cr);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    map<array<int,2>,int>mp;
    for(int i=0;i<n;++i){
        int x,y;
        cin>>x>>y;
        if(mp[{x,y}]){
            mp[{x,y}]=0;
            seg.modify(1,1,q,max(1ll,x-y+1),min(q,x+y),-1);
        }
        else{
            mp[{x,y}]=1;
            seg.modify(1,1,q,max(1ll,x-y+1),min(q,x+y),1);
        }
        // dfs(1,1,q);
        // cerr<<endl;
        cout<<fixed<<setprecision(15)<<seg.query(1,1,q)*s2<<"\n";
    }
}

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 159084kb

input:

3 10
3 2
7 3
9 6

output:

5.656854249492380
12.727922061357855
12.727922061357855

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 4ms
memory: 159364kb

input:

5 100
31 41
59 26
31 41
59 26
31 41

output:

101.823376490862844
120.208152801713079
73.539105243400943
0.000000000000000
101.823376490862844

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 8ms
memory: 159136kb

input:

100 10
6 4
2 3
7 6
5 5
3 6
7 5
5 8
10 4
9 8
0 9
9 10
9 3
2 3
10 10
8 4
10 9
0 1
1 7
0 2
3 4
10 3
3 10
7 4
7 5
1 4
0 7
1 9
5 6
8 8
7 4
8 1
3 9
2 1
5 5
2 1
10 9
8 4
0 9
10 7
4 1
9 10
8 6
5 4
1 4
0 9
9 3
4 8
5 10
7 2
8 10
7 10
3 4
2 2
8 5
0 9
5 3
1 4
6 4
0 3
8 1
1 6
3 8
8 4
6 5
10 2
2 2
8 4
6 1
2 4
6 4...

output:

11.313708498984760
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730...

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 8ms
memory: 159860kb

input:

1000 100
95 8
54 8
64 96
47 34
77 47
99 91
45 70
8 6
64 84
48 42
53 14
73 66
38 27
6 52
19 75
33 39
6 24
37 80
27 45
96 48
55 95
67 1
23 78
40 4
76 7
77 22
4 47
41 31
60 54
96 37
79 52
63 40
7 92
17 7
74 12
93 16
87 5
67 43
60 29
71 58
52 41
53 84
38 2
46 87
13 54
54 14
16 93
57 7
91 98
31 23
70 3
9...

output:

18.384776310850236
41.012193308819756
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
14...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 4ms
memory: 159864kb

input:

1000 1000
942 407
513 739
329 437
605 318
847 416
128 543
588 237
903 365
703 556
313 928
621 344
974 444
780 265
993 889
103 427
94 977
897 586
566 326
785 938
224 952
150 441
716 802
729 584
954 347
640 4
91 633
738 970
823 253
158 890
115 734
327 391
554 258
373 67
396 995
788 73
609 703
627 801
...

output:

657.609306503489198
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.213562373095049
1414.21...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 121ms
memory: 159176kb

input:

200000 10
6 4
4 9
7 9
6 2
0 7
6 7
4 8
10 5
7 8
5 4
3 6
5 9
0 9
7 3
8 2
8 6
5 9
5 10
4 9
0 3
10 5
3 9
7 2
2 3
9 7
5 6
1 7
0 4
9 6
4 7
3 8
6 4
2 7
0 6
8 3
6 2
8 10
1 6
0 4
6 1
3 3
5 8
9 7
8 7
1 10
6 2
1 8
8 6
6 1
6 3
0 6
6 1
5 6
1 1
6 4
7 9
3 5
10 6
2 8
6 7
7 3
6 8
8 5
9 7
4 5
6 4
5 10
8 6
8 5
4 6
4 6...

output:

11.313708498984760
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730950
14.142135623730...

result:

ok 200000 numbers

Test #7:

score: 0
Accepted
time: 162ms
memory: 160312kb

input:

200000 100
96 9
26 82
73 33
12 92
13 77
87 2
23 79
41 91
75 28
6 45
42 81
27 51
7 64
80 90
27 65
77 72
54 60
79 8
10 61
46 15
65 16
75 95
65 4
89 38
42 74
96 63
48 87
39 78
2 59
36 48
36 66
12 75
44 45
80 86
79 99
26 30
29 54
39 44
7 27
99 23
41 76
23 71
76 51
90 76
59 22
45 70
73 98
24 94
70 54
76 ...

output:

18.384776310850236
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
141.421356237309505
1...

result:

ok 200000 numbers

Test #8:

score: 0
Accepted
time: 260ms
memory: 172400kb

input:

200000 10000
8596 2507
1107 4452
8591 3460
3584 2911
8817 9663
1604 2760
6281 8431
5271 4811
2193 1874
5329 3970
2679 8672
8426 8447
117 4849
3471 6286
177 4806
9726 7217
6743 3882
573 4295
5291 7358
1356 6269
7882 8426
8750 985
5365 8276
7420 6372
8234 6329
7723 9014
3369 1097
7140 8329
3475 447
37...

output:

5530.989242441174736
13392.602435673210111
14142.135623730950488
14142.135623730950488
14142.135623730950488
14142.135623730950488
14142.135623730950488
14142.135623730950488
14142.135623730950488
14142.135623730950488
14142.135623730950488
14142.135623730950488
14142.135623730950488
14142.135623730...

result:

ok 200000 numbers

Test #9:

score: -100
Runtime Error

input:

200000 1000000000
979065421 937279323
384811311 879649222
673927841 883688174
47686221 518846247
805783947 475892423
94359891 104324315
116498230 496486640
155617000 261326127
423462080 949904263
758478482 824824842
594993542 173897699
495194886 158960628
409812195 339201236
958417812 891558399
7055...

output:

1355119095.862843786482699
1414213562.373095048707910
1414213562.373095048707910
1414213562.373095048707910
1414213562.373095048707910
1414213562.373095048707910
1414213562.373095048707910
1414213562.373095048707910
1414213562.373095048707910
1414213562.373095048707910
1414213562.373095048707910
141...

result: