因为我们只要最后知道答案就好了
所以我们离线
先排序，然后维护一个大根堆然后直接统计就好
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
const int N=40005;
struct Node{
int a,b,k;
Node(){}
Node(int aa,int bb,int kk){a=aa;b=bb;k=kk;}
friend bool operator<(Node A,Node B){return A.a<B.a||(A.a==B.a && A.b<B.b);}
}a[N<<1];
class Heap{
private:
priority_queue<int> P,Q;
public:
inline void I(int x){P.push(x);}
inline void D(int x){Q.push(x);}
inline int T(){while(!Q.empty() && Q.top()==P.top())P.pop(),Q.pop();return P.empty()?0:P.top();}
}H;
int n,nn;
long long ans;
void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
int main(){
freopen("4636.in","r",stdin);
freopen("4636.out","w",stdout);
Read(n);
for(int i=1;i<=n;i++){
int as,bs,ks;
Read(as);Read(bs);Read(ks);
a[++nn]=Node(as,0,ks);
a[++nn]=Node(bs,1,ks);
}
a[++nn]=Node(0,0,0);
sort(a+1,a+nn+1);
int ft=0;
for(int i=1;i<=nn;i++){
ans+=1ll*H.T()*(a[i].a-ft);
ft=a[i].a;
if(!a[i].b)H.I(a[i].k);
else H.D(a[i].k);
}
printf("%lld\n",ans);
return 0;
}
评论 (0)
