oj.uz

Submission #523648

# Submission time Handle Problem Language Result Execution time Memory
523648 2022-02-08T02:47:27 Z Deepesson Food Court (JOI21_foodcourt) C++17
24 / 100
 182 ms 134084 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 60100 KB Output is correct
2 Correct 29 ms 60264 KB Output is correct
3 Correct 29 ms 60092 KB Output is correct
4 Correct 31 ms 60228 KB Output is correct
5 Correct 31 ms 60304 KB Output is correct
6 Correct 30 ms 60180 KB Output is correct
7 Correct 30 ms 60236 KB Output is correct
8 Correct 31 ms 60236 KB Output is correct
9 Correct 30 ms 60220 KB Output is correct
10 Correct 31 ms 60288 KB Output is correct
11 Correct 30 ms 60224 KB Output is correct
12 Correct 38 ms 60256 KB Output is correct
13 Correct 37 ms 60388 KB Output is correct
14 Correct 30 ms 60364 KB Output is correct
15 Correct 29 ms 60184 KB Output is correct
16 Correct 30 ms 60292 KB Output is correct
17 Correct 30 ms 60148 KB Output is correct
18 Correct 30 ms 60236 KB Output is correct
19 Correct 30 ms 60216 KB Output is correct
20 Correct 30 ms 60276 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 60100 KB Output is correct
2 Correct 29 ms 60264 KB Output is correct
3 Correct 29 ms 60092 KB Output is correct
4 Correct 31 ms 60228 KB Output is correct
5 Correct 31 ms 60304 KB Output is correct
6 Correct 30 ms 60180 KB Output is correct
7 Correct 30 ms 60236 KB Output is correct
8 Correct 31 ms 60236 KB Output is correct
9 Correct 30 ms 60220 KB Output is correct
10 Correct 31 ms 60288 KB Output is correct
11 Correct 30 ms 60224 KB Output is correct
12 Correct 38 ms 60256 KB Output is correct
13 Correct 37 ms 60388 KB Output is correct
14 Correct 30 ms 60364 KB Output is correct
15 Correct 29 ms 60184 KB Output is correct
16 Correct 30 ms 60292 KB Output is correct
17 Correct 30 ms 60148 KB Output is correct
18 Correct 30 ms 60236 KB Output is correct
19 Correct 30 ms 60216 KB Output is correct
20 Correct 30 ms 60276 KB Output is correct
21 Incorrect 28 ms 60108 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 67964 KB Output is correct
2 Correct 146 ms 68820 KB Output is correct
3 Correct 144 ms 67964 KB Output is correct
4 Correct 136 ms 67996 KB Output is correct
5 Correct 145 ms 68804 KB Output is correct
6 Correct 153 ms 68812 KB Output is correct
7 Correct 106 ms 66004 KB Output is correct
8 Correct 96 ms 66424 KB Output is correct
9 Correct 148 ms 68272 KB Output is correct
10 Correct 140 ms 68488 KB Output is correct
11 Correct 156 ms 68516 KB Output is correct
12 Correct 142 ms 68576 KB Output is correct
13 Correct 133 ms 67424 KB Output is correct
14 Correct 182 ms 68356 KB Output is correct
15 Correct 158 ms 69844 KB Output is correct
16 Correct 153 ms 69844 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 134084 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 60100 KB Output is correct
2 Correct 29 ms 60264 KB Output is correct
3 Correct 29 ms 60092 KB Output is correct
4 Correct 31 ms 60228 KB Output is correct
5 Correct 31 ms 60304 KB Output is correct
6 Correct 30 ms 60180 KB Output is correct
7 Correct 30 ms 60236 KB Output is correct
8 Correct 31 ms 60236 KB Output is correct
9 Correct 30 ms 60220 KB Output is correct
10 Correct 31 ms 60288 KB Output is correct
11 Correct 30 ms 60224 KB Output is correct
12 Correct 38 ms 60256 KB Output is correct
13 Correct 37 ms 60388 KB Output is correct
14 Correct 30 ms 60364 KB Output is correct
15 Correct 29 ms 60184 KB Output is correct
16 Correct 30 ms 60292 KB Output is correct
17 Correct 30 ms 60148 KB Output is correct
18 Correct 30 ms 60236 KB Output is correct
19 Correct 30 ms 60216 KB Output is correct
20 Correct 30 ms 60276 KB Output is correct
21 Correct 144 ms 67964 KB Output is correct
22 Correct 146 ms 68820 KB Output is correct
23 Correct 144 ms 67964 KB Output is correct
24 Correct 136 ms 67996 KB Output is correct
25 Correct 145 ms 68804 KB Output is correct
26 Correct 153 ms 68812 KB Output is correct
27 Correct 106 ms 66004 KB Output is correct
28 Correct 96 ms 66424 KB Output is correct
29 Correct 148 ms 68272 KB Output is correct
30 Correct 140 ms 68488 KB Output is correct
31 Correct 156 ms 68516 KB Output is correct
32 Correct 142 ms 68576 KB Output is correct
33 Correct 133 ms 67424 KB Output is correct
34 Correct 182 ms 68356 KB Output is correct
35 Correct 158 ms 69844 KB Output is correct
36 Correct 153 ms 69844 KB Output is correct
37 Correct 135 ms 67052 KB Output is correct
38 Correct 124 ms 66884 KB Output is correct
39 Correct 91 ms 65404 KB Output is correct
40 Correct 109 ms 66452 KB Output is correct
41 Correct 172 ms 68100 KB Output is correct
42 Correct 166 ms 68416 KB Output is correct
43 Correct 166 ms 68344 KB Output is correct
44 Correct 160 ms 68204 KB Output is correct
45 Correct 154 ms 68360 KB Output is correct
46 Correct 162 ms 68492 KB Output is correct
47 Correct 116 ms 66272 KB Output is correct
48 Correct 123 ms 68864 KB Output is correct
49 Correct 104 ms 66104 KB Output is correct
50 Correct 124 ms 67268 KB Output is correct
51 Correct 159 ms 68620 KB Output is correct
52 Correct 144 ms 68704 KB Output is correct
53 Correct 118 ms 67804 KB Output is correct
54 Correct 155 ms 69908 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 62660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 60100 KB Output is correct
2 Correct 29 ms 60264 KB Output is correct
3 Correct 29 ms 60092 KB Output is correct
4 Correct 31 ms 60228 KB Output is correct
5 Correct 31 ms 60304 KB Output is correct
6 Correct 30 ms 60180 KB Output is correct
7 Correct 30 ms 60236 KB Output is correct
8 Correct 31 ms 60236 KB Output is correct
9 Correct 30 ms 60220 KB Output is correct
10 Correct 31 ms 60288 KB Output is correct
11 Correct 30 ms 60224 KB Output is correct
12 Correct 38 ms 60256 KB Output is correct
13 Correct 37 ms 60388 KB Output is correct
14 Correct 30 ms 60364 KB Output is correct
15 Correct 29 ms 60184 KB Output is correct
16 Correct 30 ms 60292 KB Output is correct
17 Correct 30 ms 60148 KB Output is correct
18 Correct 30 ms 60236 KB Output is correct
19 Correct 30 ms 60216 KB Output is correct
20 Correct 30 ms 60276 KB Output is correct
21 Incorrect 28 ms 60108 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 60100 KB Output is correct
2 Correct 29 ms 60264 KB Output is correct
3 Correct 29 ms 60092 KB Output is correct
4 Correct 31 ms 60228 KB Output is correct
5 Correct 31 ms 60304 KB Output is correct
6 Correct 30 ms 60180 KB Output is correct
7 Correct 30 ms 60236 KB Output is correct
8 Correct 31 ms 60236 KB Output is correct
9 Correct 30 ms 60220 KB Output is correct
10 Correct 31 ms 60288 KB Output is correct
11 Correct 30 ms 60224 KB Output is correct
12 Correct 38 ms 60256 KB Output is correct
13 Correct 37 ms 60388 KB Output is correct
14 Correct 30 ms 60364 KB Output is correct
15 Correct 29 ms 60184 KB Output is correct
16 Correct 30 ms 60292 KB Output is correct
17 Correct 30 ms 60148 KB Output is correct
18 Correct 30 ms 60236 KB Output is correct
19 Correct 30 ms 60216 KB Output is correct
20 Correct 30 ms 60276 KB Output is correct
21 Incorrect 28 ms 60108 KB Output isn't correct
22 Halted 0 ms 0 KB -