Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live

Ocultar sin cambios

Sin ajuste de línea

Vista

Nivel de detalle

Resaltado de sintaxis

Diffchecker Desktop La forma más segura de usar Diffchecker. ¡Obtén la app de Diffchecker Desktop: tus diffs nunca salen de tu computadora!Obtener Desktop

「USACO 2020.12 Platinum」Cowmistry

Creado hace 2 añosEl diff nunca expira

Los dos textos son idénticos

No hay diferencia entre estos dos textos

0 eliminaciones

Líneas
Total
Eliminado

Caracteres
Total
Eliminado

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

113 líneas

0 adiciones

Líneas
Total
Añadido

Caracteres
Total
Añadido

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

113 líneas

#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);

}

Diferencias guardadas

Texto original

Abrir archivo

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

Texto modificado

Abrir archivo

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