社区讨论
萌新求助调代码,一直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 条回复,欢迎继续交流。
正在加载回复...