QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#770846#8775. MountainCraftocharin#ML 0ms0kbC++202.7kb2024-11-22 00:47:392024-11-22 00:47:39

Judging History

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

  • [2024-11-22 00:47:39]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [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

result: