[扫描线 杂题] Codeforces Gym 101190 NEERC 16 E. Expect to Wait

智商越来越捉急

看图就知道了 答案就是阴影的面积 扫描线一波就好了

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;

inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(char &x){
for (x=nc();!(x>='+' || x<='-');x=nc());
}

const int N=500005;

int tot;
ll ans[N];

int n,Q;

struct abcd{
int f,x,y;
  abcd(int f=0,int x=0,int y=0):f(f),x(x),y(y) { }
bool operator < (const abcd &B) const{
return x<B.x;
  }
}ev[N];

int main(){
char order; int t,k,c=0;
  freopen("expect.in","r",stdin);
  freopen("expect.out","w",stdout);
  read(n); read(Q); int last=0;
for (int i=1;i<=n;i++){
    read(order); read(t); read(k);
    ev[++tot]=abcd(1,c,t-last); last=t;
if (order=='+') c+=k; else c-=k;
  }
for (int i=1;i<=Q;i++){
    read(k);
if (-k>c) ans[i]=-1;
else ev[++tot]=abcd(2,-k,i);
  }
  sort(ev+1,ev+tot+1);
  ev[0].x=ev[1].x;
  ll area=0,_t=0;
for (int i=1;i<=tot;i++){
    area+=(ll)_t*(ev[i].x-ev[i-1].x);
if (ev[i].f==1)
      _t+=ev[i].y;
else
      ans[ev[i].y]=area;
  }
for (int i=1;i<=Q;i++)
if (~ans[i])
printf("%I64d\n",ans[i]);
else
printf("INFINITY\n");
return 0;
}