Submission #19162

#	Time	Username	Problem	Language	Result	Execution time	Memory
19162		Namnamseo	Evaluation (kriii1_E)	C++14	0 / 1	775 ms	9116 KiB

E

#include <cstdio>
#include <algorithm>
using namespace std;

const int M=int(1e9)+7;

typedef long long ll;

struct seg_struct {
    static const int S=131072;
    int len [2*S];
    int sqrt[2*S]; // square tree
    int sumt[2*S]; // sum tree
    int lazy[2*S];
    int& top=sqrt[1];
    void upd(int pos,int val){
        ll newsqr = sqrt[pos];
        //printf("before sqrt %d\n",sqrt[pos]);
        newsqr += 2LL * sumt[pos] * val%M; newsqr %= M;
        //printf("delta1 %d\n",int(newsqr));
        newsqr += ((long long)val)*val%M*len[pos]%M; newsqr %= M;
        //printf("len %d, so squares %d\n",len[pos],int(newsqr));
        sqrt[pos]=newsqr;
        sumt[pos]=(sumt[pos]+len[pos]*1LL*val%M)%M;
        lazy[pos]=(lazy[pos]+val)%M;
        //printf("Updating %d; value %d\n",pos,int(newsqr));
    }
    void pd(int pos,int myl,int myr){
        if(pos >= S || lazy[pos]==0) return;
        upd(pos*2,lazy[pos]);
        upd(pos*2+1,lazy[pos]);
        lazy[pos]=0;
    }
    void update(int l,int r,int val,int pos=1,int myl=0,int myr=S-1){
        pd(pos,myl,myr);
        if(r<myl || myr<l) return;
        else if(l<=myl && myr<=r){
            upd(pos,val);
        } else {
            int mid=(myl+myr)/2;
            update(l,r,val,pos*2  ,myl  ,mid);
            update(l,r,val,pos*2+1,mid+1,myr);
            sqrt[pos] = (sqrt[pos*2]+sqrt[pos*2+1])%M;
            sumt[pos] = (sumt[pos*2]+sumt[pos*2+1])%M;
        }
    }
} seg;

struct updquery {
    int l,r;
    int pos;
    int value;
} query [200010];

int ycomp [200010];

int n;

void read(int& a){ scanf("%d",&a); }
void read(long long& a){ scanf("%I64d",&a); }
void read(char*& a){ scanf("%s",a); }
template<typename T,typename... Args> void read(T& a,Args&... args){ read(a); read(args...); }

int main()
{
    int i,a,b,c,d,v;
    read(n);
    for(i=0;i<n;++i){
        read(a,c,b,d,v);
        //printf("range %d~%d, pos %d~%d\n",a,b,c,d);
        ycomp[i*2]   = a;
        ycomp[i*2+1] = b+1;
        query[i*2]   = {a,b+1,  c, v};
        query[i*2+1] = {a,b+1,d+1,M-v};
    }
    sort(query, query+2*n, [](const updquery& a,const updquery& b){ return a.pos < b.pos; });
    sort(ycomp, ycomp+2*n);
    int ynn = unique(ycomp, ycomp+2*n)-ycomp;
    for(i=0;i+1<ynn;++i){
        seg.len[seg.S+i]=ycomp[i+1]-ycomp[i];
    }
    for(i=seg.S-1;1<=i;--i) seg.len[i]=seg.len[i*2]+seg.len[i*2+1];
    int ans = 0;
    for(i=0;i<2*n;++i){
        auto& cq=query[i];
        if(i) ans = (ans + (cq.pos-query[i-1].pos)*1LL*seg.top%M)%M;
        int l=lower_bound(ycomp, ycomp+ynn, cq.l)-ycomp;
        int r=lower_bound(ycomp, ycomp+ynn, cq.r)-ycomp;
        //printf("Update %d~%d %d~%d pos %d v %d\n",l,r-1,cq.l,cq.r,cq.pos,cq.value);
        seg.update(l, r-1, cq.value);
        //printf("pos %d, top %d\n",cq.pos,seg.top);
        //putchar(10);
    }
    printf("%d\n",ans);
    return 0;
}

• Subtask 1: 0 / 1