Submission #1010633

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1010633	2024-06-29T08:48:24 Z	ivopav	Luxury burrow (IZhO13_burrow)	C++17	0 / 100	2000 ms	5804 KB

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(){
    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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 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	432 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	26 ms	348 KB	Output is correct
9	Correct	60 ms	672 KB	Output is correct
10	Correct	126 ms	856 KB	Output is correct
11	Correct	240 ms	1308 KB	Output is correct
12	Correct	187 ms	908 KB	Output is correct
13	Correct	145 ms	856 KB	Output is correct
14	Correct	523 ms	1900 KB	Output is correct
15	Correct	543 ms	1880 KB	Output is correct
16	Correct	517 ms	2384 KB	Output is correct
17	Correct	921 ms	1876 KB	Output is correct
18	Correct	1580 ms	5804 KB	Output is correct
19	Execution timed out	2003 ms	5268 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-