oj.uz

Submission #705786

# Submission time Handle Problem Language Result Execution time Memory
705786 2023-03-05T08:54:59 Z Abito 3D Histogram (COCI20_histogram) C++17
20 / 110
 2500 ms 85968 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
typedef unsigned long long ull;
using namespace std;
const int N=2e5+5;
int a[N],b[N],stv[2][25][N],st[25][N],lg[N],n;
void buildv(){
    for (int i=1;i<=n;i++) stv[0][0][i]=a[i];
    for (int i=1;i<=n;i++) stv[1][0][i]=b[i];
    for (int i=1;i<25;i++){
        for (int j=1;j+(1<<i)<=n+1;j++){
            stv[0][i][j]=min(stv[0][i-1][j],stv[0][i-1][j+(1<<(i-1))]);
            stv[1][i][j]=min(stv[1][i-1][j],stv[1][i-1][j+(1<<(i-1))]);
        }
    }
}
int queryv(int l,int r){
    int i=lg[r-l+1];
    return min(stv[0][i][l],stv[0][i][r-(1<<i)+1])*min(stv[1][i][l],stv[1][i][r-(1<<i)+1])*(r-l+1);
}
/*void build(){
    for (int i=0;i<25;i++){
        for (int j=1;j+(1<<i)<=n+1;j++){
            st[i][j]=queryv(j,j+(1<<i)-1);
        }
    }
    return;
}
int query(int l,int r){
    int i=lg[r-l+1];
    return max(st[i][l],st[i][r-(1<<i)+1]);
}*/
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    for (int i=2;i<N;i++) lg[i]=lg[i/2]+1;
    for (int i=0;i<2;i++){
        for (int j=0;j<25;j++){
            for (int k=0;k<N;k++) stv[i][j][k]=INT_MAX;
        }
    }
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i]>>b[i];
    buildv();
    //build();
    int ans=0;
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++) ans=max(ans,queryv(i,j));
    }cout<<ans<<endl;
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 80204 KB Output is correct
2 Correct 40 ms 80232 KB Output is correct
3 Correct 38 ms 80104 KB Output is correct
4 Correct 39 ms 80192 KB Output is correct
5 Correct 37 ms 80172 KB Output is correct
6 Correct 39 ms 80212 KB Output is correct
7 Correct 37 ms 80204 KB Output is correct
8 Correct 39 ms 80172 KB Output is correct
9 Correct 45 ms 80288 KB Output is correct
10 Correct 42 ms 80104 KB Output is correct
11 Correct 31 ms 80084 KB Output is correct
12 Correct 38 ms 80212 KB Output is correct

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 80204 KB Output is correct
2 Correct 40 ms 80232 KB Output is correct
3 Correct 38 ms 80104 KB Output is correct
4 Correct 39 ms 80192 KB Output is correct
5 Correct 37 ms 80172 KB Output is correct
6 Correct 39 ms 80212 KB Output is correct
7 Correct 37 ms 80204 KB Output is correct
8 Correct 39 ms 80172 KB Output is correct
9 Correct 45 ms 80288 KB Output is correct
10 Correct 42 ms 80104 KB Output is correct
11 Correct 31 ms 80084 KB Output is correct
12 Correct 38 ms 80212 KB Output is correct
13 Execution timed out 2577 ms 85968 KB Time limit exceeded
14 Halted 0 ms 0 KB -