Compare text

Find the difference between two text files

Real-time diff

Unified diff

Collapse lines

Highlight change

Syntax highlighting

Tools

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

Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Download Diffchecker Desktop Learn more

「USACO 2020.12 Platinum」Cowmistry

Created 3 months agoDiff never expires

The two files are identical

There is no difference to show between these two files

0 removals

113 lines

0 additions

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; }