# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
3114 | ainta | Evaluation (kriii1_E) | C++98 | 0 ms | 4336 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<stdio.h>
#include<algorithm>
using namespace std;
long long Mod=1000000007;
struct SegTree{
SegTree(){
S=0,p=0,c1=c2=NULL;
}
long long S;
int p;
SegTree *c1,*c2;
};
struct Seg{
int x,y1,y2,p;
bool operator <(const Seg &p)const{
return x<p.x;
}
}Y[200001];
int n,i,c;
long long S,T,Res;
void push(int x,int y1,int y2,int p){
Y[c].x=x,Y[c].y1=y1,Y[c].y2=y2,Y[c].p=p;
c++;
}
void spread(SegTree *node,int b,int e,int m){
long long p=node->p;
node->p=0;
node->c1->S+=p*(m-b+1);
node->c2->S+=p*(e-m);
node->c1->p+=p,node->c2->p+=p;
}
void make_child(SegTree *node){
node->c1=new SegTree();
node->c2=new SegTree();
}
long long Sum(SegTree *node,int b,int e,int s,int l){
if(b==s && e==l){
return node->S;
}
int m=(b+e)>>1;
if(node->c1==NULL){
return (long long)node->p*(e-b+1);
}
if(node->p)spread(node,b,e,m);
long long ss=0;
if(m>=s){
ss+=Sum(node->c1,b,m,s,min(m,l));
}
if(m+1<=l){
ss+=Sum(node->c2,m+1,e,max(s,m+1),l);
}
return ss;
}
void Ins(SegTree *node,int b,int e,int s,int l,int p){
if(b==s && e==l){
node->S+=(long long)(e-b+1)*p;
node->p+=p;
return;
}
int m=(b+e)>>1;
if(node->c1==NULL)make_child(node);
if(node->p)spread(node,b,e,m);
if(m>=s){
Ins(node->c1,b,m,s,min(m,l),p);
}
if(m+1<=l){
Ins(node->c2,m+1,e,max(s,m+1),l,p);
}
node->S=node->c1->S+node->c2->S;
}
int main()
{
int x1,y1,x2,y2,a;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&a);
push(x1,y1,y2,a);
push(x2+1,y1,y2,-a);
}
sort(Y,Y+c);
SegTree *root=new SegTree();
for(i=0;i<c;i++){
S+=(long long)(Y[i].y2-Y[i].y1+1)*Y[i].p*Y[i].p;
T=(Mod+Y[i].p)%Mod;
S+=Sum(root,1,1000000000,Y[i].y1,Y[i].y2)%Mod*T*2LL;
S%=Mod;
Ins(root,1,1000000000,Y[i].y1,Y[i].y2,Y[i].p);
if(i!=c-1 && Y[i].x!=Y[i+1].x){
Res+=S*(Y[i+1].x-Y[i].x);
Res%=Mod;
}
}
printf("%lld\n",Res);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |