Compare text

Find the difference between two text files

Real-time editor

Hide unchanged lines

Disable line wrap

Layout

Diff precision

Syntax highlighting

Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

「USACO 2020.12 Platinum」Cowmistry

Created 2 years agoDiff never expires

The two texts are identical

There is no difference to show between these two texts

0 removals

Lines
Total
Removed

Characters
Total
Removed

To continue using this feature, upgrade to Diffchecker Pro View Pricing

113 lines

0 additions

Lines
Total
Added

Characters
Total
Added

To continue using this feature, upgrade to Diffchecker Pro View Pricing

113 lines

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair <int,int> Pii;

#define mp make_pair

#define pb push_back

#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)

#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;

int rd(){

int s=0;

while(!isdigit(IO=getchar()));

do s=(s<<1)+(s<<3)+(IO^'0');

while(isdigit(IO=getchar()));

return s;

}

const int N=2e4+10,P=1e9+7,I2=(P+1)/2,I3=(P+1)/3,U=1<<30;

int n,m,k;

int L[N],R[N];

int Check(){

for(int i=k;i;i>>=1) if(~i&1) return 0;

return 1;

}

int D3(int n){ return 1ll*n*(n-1)/2%P*(n-2)%P*I3%P; }

int D2(int n){ return 1ll*n*(n-1)/2%P; }

const int M=N*60;

int s[M],ls[M],rs[M],t[M],cnt,rt;

//在线段树上插入节点，打上标记，同时处理出size便于下面计算

void Ins(int &p,int l,int r,int ql,int qr){

if(!p) p=++cnt;

s[p]+=min(qr,r)-max(ql,l)+1;

if(ql<=l && r<=qr) { t[p]=1; return; }

int mid=(l+r)>>1;

if(ql<=mid) Ins(ls[p],l,mid,ql,qr);

if(qr>mid) Ins(rs[p],mid+1,r,ql,qr);

}

int ans;

// O(1)求出m

int Up(int k){ return 1<<(32-__builtin_clz(k)); }

typedef vector <Pii> V;

V Union(const V &A,const V &B){

int p1=0,p2=0,s1=A.size(),s2=B.size();

V R;

// 这里是否归并并不影响复杂度

while(p1<s1 || p2<s2) {

if(p1<s1 && (p2==s2||A[p1]<B[p2])) {

if(R.size() && R.back().first==A[p1].first) R.back().second+=A[p1].second;

else R.pb(A[p1]);

p1++;

} else {

if(R.size() && R.back().first==B[p2].first) R.back().second+=B[p2].second;

else R.pb(B[p2]);

p2++;

}

return R;

}

V Calc(int a,int b,int L,int k,int f1,int f2){

f1|=t[a],f2|=t[b];

V Res;

// 底层情况O(1)解决

if(!f1 && !a) return Res;

if(f2) return Res.pb(mp(k+1,f1?L:s[a])),Res;

if(!b) return Res.pb(mp(0,f1?L:s[a])),Res;

int m=Up(k);

// L>m说明还要继续进行分裂

if(L>m) return Union(Calc(ls[a],ls[b],L/2,k,f1,f2),Calc(rs[a],rs[b],L/2,k,f1,f2));

// 进入降阶子问题，左查右，右查左

k-=m/2;

V A=Calc(ls[a],rs[b],L/2,k,f1,f2);

for(auto &i:A) i.first+=f2?L/2:s[ls[b]];

V B=Calc(rs[a],ls[b],L/2,k,f1,f2);

for(auto &i:B) i.first+=f2?L/2:s[rs[b]];

return Union(A,B);

}

int cm;

// 第一次分裂

void Solve(int p,int L){

if(!p) return;

// 完全覆盖的部分答案可以快速求出

if(t[p]) { cm+=L/m; return; }

// 已经完成分裂，此时进入第一层子问题

if(L==m) {

// 贡献分为

// 左选3 ，右选 3

ans=(ans+D3(s[ls[p]]))%P,ans=(ans+D3(s[rs[p]]))%P;

// 左1，右2

V A=Calc(ls[p],rs[p],m/2,k-m/2,0,0);

// 左2，右1

V B=Calc(rs[p],ls[p],m/2,k-m/2,0,0);

for(auto i:A) ans=(ans+1ll*D2(i.first)*i.second)%P;

for(auto i:B) ans=(ans+1ll*D2(i.first)*i.second)%P;

return;

}

Solve(ls[p],L/2),Solve(rs[p],L/2);

}

int main(){

n=rd(),k=rd();

rep(i,1,n) { int l=rd(),r=rd(); Ins(rt,0,U-1,l,r); }

m=Up(k),Solve(rt,U);

// O(1)求得完全覆盖部分的答案

int t=(2ll*D3(m/2)+1ll*D2(k-m/2+1)*m)%P;

ans=(ans+1ll*cm*t)%P;

printf("%d\n",ans);

}

Saved diffs

Original text

Open file

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
    int s=0;
    while(!isdigit(IO=getchar()));
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return s;
}

const int N=2e4+10,P=1e9+7,I2=(P+1)/2,I3=(P+1)/3,U=1<<30;

int n,m,k;
int L[N],R[N];
int Check(){
    for(int i=k;i;i>>=1) if(~i&1) return 0;
    return 1;
}
int D3(int n){ return 1ll*n*(n-1)/2%P*(n-2)%P*I3%P; }
int D2(int n){ return 1ll*n*(n-1)/2%P; }

const int M=N*60;
int s[M],ls[M],rs[M],t[M],cnt,rt;
//在线段树上插入节点，打上标记，同时处理出size便于下面计算
void Ins(int &p,int l,int r,int ql,int qr){
    if(!p) p=++cnt;
    s[p]+=min(qr,r)-max(ql,l)+1;
    if(ql<=l && r<=qr) { t[p]=1; return; }
    int mid=(l+r)>>1;
    if(ql<=mid) Ins(ls[p],l,mid,ql,qr);
    if(qr>mid) Ins(rs[p],mid+1,r,ql,qr);
}

int ans;
// O(1)求出m
int Up(int k){ return 1<<(32-__builtin_clz(k)); }
typedef vector <Pii> V;
V Union(const V &A,const V &B){
    int p1=0,p2=0,s1=A.size(),s2=B.size();
    V R;
    // 这里是否归并并不影响复杂度
    while(p1<s1 || p2<s2) {
        if(p1<s1 && (p2==s2||A[p1]<B[p2])) {
            if(R.size() && R.back().first==A[p1].first) R.back().second+=A[p1].second;
            else R.pb(A[p1]);
            p1++;
        } else {
            if(R.size() && R.back().first==B[p2].first) R.back().second+=B[p2].second;
            else R.pb(B[p2]);
            p2++;
        }
    }
    return R;
}
V Calc(int a,int b,int L,int k,int f1,int f2){
    f1|=t[a],f2|=t[b];
    V Res;
    // 底层情况O(1)解决
    if(!f1 && !a) return Res;
    if(f2) return Res.pb(mp(k+1,f1?L:s[a])),Res;
    if(!b) return Res.pb(mp(0,f1?L:s[a])),Res;
    int m=Up(k);
    // L>m说明还要继续进行分裂
    if(L>m) return Union(Calc(ls[a],ls[b],L/2,k,f1,f2),Calc(rs[a],rs[b],L/2,k,f1,f2));
    // 进入降阶子问题，左查右，右查左
    k-=m/2;
    V A=Calc(ls[a],rs[b],L/2,k,f1,f2);
    for(auto &i:A) i.first+=f2?L/2:s[ls[b]];
    V B=Calc(rs[a],ls[b],L/2,k,f1,f2);
    for(auto &i:B) i.first+=f2?L/2:s[rs[b]];
    return Union(A,B);
}

int cm;
// 第一次分裂
void Solve(int p,int L){
    if(!p) return;
    // 完全覆盖的部分答案可以快速求出
    if(t[p]) { cm+=L/m; return; }
    // 已经完成分裂，此时进入第一层子问题
    if(L==m) {
        // 贡献分为 
        // 左选3 ， 右选 3
        ans=(ans+D3(s[ls[p]]))%P,ans=(ans+D3(s[rs[p]]))%P;
        // 左1，右2
        V A=Calc(ls[p],rs[p],m/2,k-m/2,0,0);
        // 左2，右1
        V B=Calc(rs[p],ls[p],m/2,k-m/2,0,0);
        for(auto i:A) ans=(ans+1ll*D2(i.first)*i.second)%P;
        for(auto i:B) ans=(ans+1ll*D2(i.first)*i.second)%P;
        return;
    }
    Solve(ls[p],L/2),Solve(rs[p],L/2);
}
int main(){
    n=rd(),k=rd();
    rep(i,1,n) { int l=rd(),r=rd(); Ins(rt,0,U-1,l,r); }
    m=Up(k),Solve(rt,U);
    // O(1)求得完全覆盖部分的答案
    int t=(2ll*D3(m/2)+1ll*D2(k-m/2+1)*m)%P;
    ans=(ans+1ll*cm*t)%P;
    printf("%d\n",ans);
}

Changed text

Open file

const int N=2e4+10,P=1e9+7,I2=(P+1)/2,I3=(P+1)/3,U=1<<30;

int n,m,k;
int L[N],R[N];
int Check(){
    for(int i=k;i;i>>=1) if(~i&1) return 0;
    return 1;
}
int D3(int n){ return 1ll*n*(n-1)/2%P*(n-2)%P*I3%P; }
int D2(int n){ return 1ll*n*(n-1)/2%P; }