# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
3860 | cki86201 | Evaluation (kriii1_E) | C++98 | 8 ms | 7376 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<algorithm>
const int M=1000000007;
struct node{
int add, tot, sum;
node* left, *right;
node(){ left = right = 0; add=tot=sum=0; }
};
struct segment{
int s,e,y,su;
bool operator<(const segment &l)const{
return y<l.y;
}
};
struct SegmentTree{
node* root;
int start, end;
SegmentTree(){}
SegmentTree(int start, int end):start(start),end(end){ root = new node(); }
void DFS(node* n, int s, int e, int l, int r, int su) // s-e: node가 담당하는 구간, l-r: 갱신하려는 구간
{
long long cnt=e-s+1;
if(e < l || r < s ) return; // 구간이 겹치지 않는 경우
if(l <= s && e <= r){
n->add += su;
if(!n->left){
n->sum=(cnt*n->add)%M;
n->tot=(((cnt*n->add)%M)*n->add)%M;
}
else{
n->sum=((long long)n->left->sum+n->right->sum+(cnt*n->add)%M)%M;
n->tot=((long long)n->left->tot+n->right->tot+((long long)n->add*((2ll*n->sum-(cnt*n->add)%M)%M)%M)%M)%M;
}
return;
}
// 나머지
if( !n->left ) n->left = new node(), n->right = new node();
int m = ( s + e ) / 2;
DFS(n->left, s, m, l, r, su);
DFS(n->right, m+1, e, l, r, su);
n->sum=((long long)n->left->sum+n->right->sum+(cnt*n->add)%M)%M;
n->tot=((long long)n->left->tot+n->right->tot+((long long)n->add*((2ll*n->sum-(cnt*n->add)%M)%M)%M)%M)%M;
}
void insert(int left, int right,int su)
{
DFS(root, start, end, left, right, su);
}
long long read()
{
return root->tot;
}
}Tree=SegmentTree(0,1000000500);
segment data[200005];
int n;
int main()
{
int i,a,b,c,d,e;
long long ans=0;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
data[2*i].s=a; data[2*i].e=c; data[2*i].su=e; data[2*i].y=b;
data[2*i+1].s=a; data[2*i+1].e=c; data[2*i+1].su=-e; data[2*i+1].y=d+1;
}
std::sort(data,data+2*n);
Tree.insert(data[0].s,data[0].e,data[0].su);
for(int i=1;i<2*n;i++){
ans+=(Tree.read()*(data[i].y-data[i-1].y))%M;
Tree.insert(data[i].s,data[i].e,data[i].su);
ans%=M;
}
ans%=M;
printf("%lld",ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |