Submission #523648

#	Time	Username	Problem	Language	Result	Execution time	Memory
523648		Deepesson	Food Court (JOI21_foodcourt)	C++17	24 / 100	182 ms	134084 KiB

foodcourt

#include <bits/stdc++.h>
#define MAX 305000
using ll = long long;
typedef std::array<std::array<ll,2>,2> matriz;
matriz mul(matriz a,matriz b){
    matriz c = {};
    for(auto&x:c)for(auto&y:x)y=(-1LL<<60LL);
    for(int i=0;i!=2;++i){
        for(int j=0;j!=2;++j){
            for(int k=0;k!=2;++k){
                c[i][j]=std::max(c[i][j],a[i][k]+b[k][j]);
            }
        }
    }
    return c;
}
matriz montar(long long X){
    matriz u = {};
    for(auto&x:u)for(auto&y:x)y=(-(1LL<<60LL));
    u[0][0]=X;
    u[1][1]=0;
    u[1][0]=0;
    return u;
}
matriz neutro,base;
matriz tab[MAX*4];
void update(int t,matriz g,int la=0,int ra=MAX-1,int pos=1){
    if(t>ra||la>t)return;
    if(la==ra){
        tab[pos]=g;
        return;
    }
    int m = (la+ra)/2;
    update(t,g,la,m,pos*2);
    update(t,g,m+1,ra,(pos*2)+1);
 /*   std::cout<<"Tem "<<tab[pos*2][0][0]<<" "<<tab[(pos*2)+1][0][0]<<"\n";
    for(int i=0;i!=2;++i){
        for(int j=0;j!=2;++j){
            std::cout<<tab[pos*2][i][j]<<" ";
        }
        std::cout<<"\n";
    }
    std::cout<<"Direita:\n";
    for(int i=0;i!=2;++i){
        for(int j=0;j!=2;++j){
            std::cout<<tab[(pos*2)+1][i][j]<<" ";
        }
        std::cout<<"\n";
    }
    std::cout<<"\n";*/
    tab[pos]=mul(tab[pos*2],tab[(pos*2)+1]);
   /// std::cout<<"Atualiza "<<tab[pos][0][0]<<"\n";
}
matriz query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
    if(l>ra||la>r)return neutro;
    if(la>=l&&ra<=r){
        return tab[pos];
    }
    int m=(la+ra)/2;
    return mul(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
}
long long ft[MAX];
#define LSB(A) (A&(-A))
void add(long long x,long long y){
    x+=6;
    while(x<MAX){
        ft[x]+=y;
        x+=LSB(x);
    }
}
ll query(long long x){
    x+=6;
    ll ans=0;
    while(x>0){
        ans+=ft[x];
        x-=LSB(x);
    }
    return ans;
}
typedef std::pair<int,matriz> pim;
typedef std::pair<int,int> pii;
typedef std::pair<pii,int> ppi;
std::vector<pim> matupdate[MAX];
std::vector<pii> ftupdate[MAX];
std::vector<ppi> queries[MAX];
int grupo[MAX];
int respostas[MAX];
int main()
{
    neutro[0][1]=neutro[1][0]=(-(1LL<<60LL));
    for(auto&x:tab)x=neutro;
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int N,M,Q;
    std::cin>>N>>M>>Q;
    int cur=0;
    for(int i=0;i!=Q;++i){
        int t;
        std::cin>>t;
        if(t==1){
            int L,R,C,K;
            std::cin>>L>>R>>C>>K;
            --L;
            grupo[i]=C;
            ftupdate[L].push_back({i,K});
            ftupdate[R].push_back({i,-K});
            matupdate[L].push_back({i,montar(K)});
            matupdate[R].push_back({i,neutro});
        }else if(t==2){
            int L,R,K;
            std::cin>>L>>R>>K;
            --L;
            matupdate[L].push_back({i,montar(-K)});
            matupdate[R].push_back({i,neutro});
        }else {
            int A,B;
            std::cin>>A>>B;--A;
            queries[A].push_back({{B,i},cur});
            ++cur;
        }
    }
    for(int i=0;i!=M+5;++i){
        for(auto&x:ftupdate[i]){
            add(x.first,x.second);
        }
        for(auto&x:matupdate[i]){
        ///    std::cout<<"Add "<<x.first<<" "<<x.second[0][0]<<"\n";
            update(x.first,x.second);
         ///   std::cout<<"Novo "<<tab[1][0][0]<<"\n";
        }
        for(auto&x:queries[i]){
            long long escolhido = x.first.first;
            long long tempo = x.first.second;
            long long indice = x.second;
            matriz q = mul(base,query(0,tempo));
            long long nafila = q[0][0];
         ///   std::cout<<"Na fila: "<<nafila<<" "<<tempo<<"\n";
            if(nafila<escolhido){
                respostas[indice]=0;
                continue;
            }
            long long soma = query(tempo);
            long long retirar = nafila-escolhido;
            long long pegar = soma - retirar;
          ///  std::cout<<soma<<" "<<nafila<<"\n";
            long long l=0,r=tempo;
            while(l<r){
                long long m = (l+r)/2;
                long long g = query(m);
                if(g>=pegar){
                    r=m;
                }else l=m+1;
            }
          ///  std::cout<<"Achou "<<l<<"\n";
            respostas[indice]=grupo[l];
        }
    }

    for(int i=0;i!=cur;++i){
        std::cout<<respostas[i]<<"\n";
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 21
• Subtask 5: 15 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11