oj.uz

답안 #1010633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010633 2024-06-29T08:48:24 Z ivopav 호화 벙커 (IZhO13_burrow) C++17
0 / 100
 2000 ms 5804 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(){
    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

# 결과 실행 시간 메모리 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 -