QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#770844 | #8775. MountainCraft | ocharin# | RE | 260ms | 172400kb | C++20 | 2.7kb | 2024-11-22 00:46:09 | 2024-11-22 00:46:10 |
Judging History
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...