Submission #19162

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19162	2016-02-19T08:19:31 Z	Namnamseo	Evaluation (kriii1_E)	C++14	0 / 1	775 ms	9116 KB

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.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9116 KB	Output is correct
2	Correct	0 ms	9116 KB	Output is correct
3	Correct	0 ms	9116 KB	Output is correct
4	Correct	0 ms	9116 KB	Output is correct
5	Correct	1 ms	9116 KB	Output is correct
6	Correct	4 ms	9116 KB	Output is correct
7	Correct	3 ms	9116 KB	Output is correct
8	Correct	6 ms	9116 KB	Output is correct
9	Correct	6 ms	9116 KB	Output is correct
10	Correct	3 ms	9116 KB	Output is correct
11	Correct	30 ms	9116 KB	Output is correct
12	Correct	43 ms	9116 KB	Output is correct
13	Correct	63 ms	9116 KB	Output is correct
14	Correct	74 ms	9116 KB	Output is correct
15	Correct	72 ms	9116 KB	Output is correct
16	Correct	307 ms	9116 KB	Output is correct
17	Correct	427 ms	9116 KB	Output is correct
18	Correct	607 ms	9116 KB	Output is correct
19	Incorrect	775 ms	9116 KB	Output isn't correct
20	Halted	0 ms	0 KB	-