社区讨论

萌新求助调代码,一直WA on #5

CF609F Frogs and mosquitoes参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lyl5ljha
此快照首次捕获于
2024/07/14 14:07
2 年前
此快照最后确认于
2024/07/14 15:47
2 年前
查看原帖
我用的ODT维护,蚊子用multiset,代码应该比较好读懂(
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
const int N = 2e5+5;
int ans[N],pos[N],id[N],n,m,rt;
ll len[N];
multiset<pair<int,int> > wz;
bool cmp(int x,int y)
{return pos[x] < pos[y];}
struct node
{
    ll l,r;mutable int v;
    friend bool operator < (node x,node y)
    {return x.l < y.l;}
};set<node> s;
auto split(ll pos)
{
    auto it = --s.upper_bound({pos,0,0});
    node x = *it;if(x.l == pos)return it;
    s.erase(it);s.insert({x.l,pos-1,x.v});
    return s.insert({pos,x.r,x.v}).first;
}
void assign(ll l,ll r,int v)
{
    auto itr = split(r+1),itl = split(l);
    s.erase(itl,itr);s.insert({l,r,v});
}
int get(ll pos)
{auto it = --s.upper_bound({pos,0,0});return it->v;}
inline int rd()
{
    char c;int f = 1;
    while(!isdigit(c = getchar()))if(c=='-')f = -1;
    int x = c-'0';
    while(isdigit(c = getchar()))x = x*10+(c^48);
    return x*f;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n = rd();m = rd();s.insert({0,(ll)3e14,0});
    for(int i = 1;i <= n;i++)
        pos[i] = rd(),len[i] = rd(),id[i] = i;
    sort(id+1,id+n+1,cmp);
    for(int i = n;i;i--)
        assign(pos[id[i]],pos[id[i]]+len[id[i]],id[i]);
    while(m--)
    {
        int p = rd(),b = rd();
        int x = get(p);
        if(x)
        {
            auto it = wz.lower_bound({pos[x]+len[x]+1,0});
            ans[x]++;len[x] += b;
            for(;it != wz.end()&&it->first <= pos[x]+len[x];it = wz.erase(it))
                ans[x]++,len[x] += it->second;
            assign(pos[x],pos[x]+len[x],x);
        }
        else wz.insert({p,b});
    }
    for(int i = 1;i <= n;i++)
        printf("%d %lld\n",ans[i],len[i]);
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...