oj.uz

Submission #1010635

# Submission time Handle Problem Language Result Execution time Memory
1010635 2024-06-29T08:49:47 Z ivopav Luxury burrow (IZhO13_burrow) C++17
0 / 100
 2000 ms 9556 KB 
#include <bits/stdc++.h>
using namespace std;

void upd(vector<pair<int,int>>& tour,int ind,int val,int ofs){
    tour[ind].first=val;
    while (ind>0){
        ind/=2;
        tour[ind]=min(tour[ind*2],tour[ind*2+1]);
    }
}

pair<int,int> que(vector<pair<int,int>>& tour,int ind,int ofs,int l,int r,int l2,int r2){
    if (r<l2 || r2<l){
        return {1e9,1e9};
    }
    if (l<=l2 && r2<=r){
        return tour[ind];
    }
    return min(que(tour,ind*2,ofs,l,r,l2,(l2+r2)/2),que(tour,ind*2+1,ofs,l,r,(l2+r2)/2+1,r2));
}

int dq(int l,int r,vector<pair<int,int>>& tour,int ofs){
    if (l>r){
        return 0;
    }
    pair<int,int> pom=que(tour,1,ofs,l,r,0,ofs-1);
  //  cout << l << " " << pom.second << " " << r << "++\n";
//    cout << pom.first << "--\n";
    int rje1=pom.first*(r-l+1);
    int rje2=dq(l,pom.second-1,tour,ofs);
    int rje3=dq(pom.second+1,r,tour,ofs);
    return max(rje1,max(rje2,rje3));
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    int m;
    int k;
    cin >> n >> m >> k;
    vector<vector<int>> mat={};
    for (int i=0;i<n;i++){
        mat.push_back({});
        for (int j=0;j<m;j++){
            int unos;
            cin >> unos;
            mat[i].push_back(unos);
        }
    }
    int l=1;
    int r=1e9+1;
    int mid=5e8;
    int ofs=1;
    while (ofs<n){
        ofs*=2;
    }
    int rje=0;
    while (l<mid){
     //   cout << mid << "-----------\n";
        vector<vector<bool>> mat2={};
        for (int i=0;i<n;i++){
            mat2.push_back({});
            for (int j=0;j<m;j++){
                if (mat[i][j]>=mid){
                    mat2[i].push_back(1);
                }
                else {
                    mat2[i].push_back(0);
                }
            }
        }
   //     cout << mid << "\n";
        vector<pair<int,int>> tour(ofs*2,{0,0});
        for (int i=ofs;i<ofs*2;i++){
            tour[i].second=i-ofs;
        }
        for (int i=ofs-1;i>0;i--){
            tour[i]=min(tour[i*2],tour[i*2+1]);
        }
       // cout << mid << "\n";
        int najv=0;
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
     //           cout << j << "\n";
                if (tour[ofs+j].first>0){
                    upd(tour,ofs+j,tour[ofs+j].first-1,ofs);
                }
                else if (mat2[j][i]){
                    int kol=0;
                    int sad=i;
                    while (sad<m && mat2[j][sad]){
                        kol++;
                        sad++;
                    }
           //         if (sad>0){
         //               cout << i << " " << j << " " << kol << "+++__+_+_____+\n";
      ///              }
                    upd(tour,ofs+j,kol,ofs);
                }
            }
    //        cout << i << "\n";
            //for (int j=0;j<ofs*2;j++){
          //      cout << tour[j].first << " " << tour[j].second << "\n";
        //    }
            najv=max(najv,dq(0,n-1,tour,ofs));
        }
      //  cout << najv << "+++++++++\n";
        if (najv>=k){
            l=mid;
            rje=najv;   
        }
        else {
            r=mid;
        }
        mid=(l+r)/2;
    }
    cout << mid << " " << rje << "\n";
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 23 ms 536 KB Output is correct
9 Correct 52 ms 684 KB Output is correct
10 Correct 117 ms 860 KB Output is correct
11 Correct 212 ms 1116 KB Output is correct
12 Correct 165 ms 928 KB Output is correct
13 Correct 130 ms 1116 KB Output is correct
14 Correct 472 ms 1884 KB Output is correct
15 Correct 520 ms 1880 KB Output is correct
16 Correct 503 ms 2432 KB Output is correct
17 Correct 852 ms 2072 KB Output is correct
18 Correct 1385 ms 5344 KB Output is correct
19 Correct 1854 ms 5456 KB Output is correct
20 Execution timed out 2065 ms 9556 KB Time limit exceeded
21 Halted 0 ms 0 KB -