QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#770846 | #8775. MountainCraft | ocharin# | ML | 0ms | 0kb | C++20 | 2.7kb | 2024-11-22 00:47:39 | 2024-11-22 00:47:39 |
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<<6);
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: 0
Memory Limit Exceeded
input:
3 10 3 2 7 3 9 6
output:
5.656854249492380 12.727922061357855 12.727922061357855