Submission #1010635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010635		ivopav	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	2065 ms	9556 KiB

burrow

#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