제출 #267183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
267183		doowey	Rectangles (IOI19_rect)	C++14	59 / 100	5068 ms	196016 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using namespace std;

typedef long long ll;
typedef pair<short, short> pii;

#define fi first
#define se second
#define mp make_pair

const short N = 2505;

struct segtree{
    vector<short> ele;
    short mode;
    short n;
    void init(short sz, short md){
        mode = md;
        n = sz;
        if(md == 0)
            ele.resize(2 * n, 5000);
        else
            ele.resize(2 * n, -1);
    }
    void upd(short id, short v){
        id += n;
        if(mode == 0)
            ele[id] = min(ele[id], v);
        else
            ele[id] = max(ele[id], v);
        id >>= 1;
        while(id > 0){
            if(mode == 0) ele[id] = min(ele[id << 1], ele[id << 1 | 1]);
            else ele[id] = max(ele[id << 1], ele[id << 1 | 1]);
            id >>= 1;
        }
    }
    short get(short l, short r){
        l += n;
        r += n;
        short res = -1;
        if(mode == 0) res = 5000;
        while(l <= r){
            if((l & 1)){
                if(mode == 0) res = min(res, ele[l]);
                else res = max(res, ele[l]);
                l ++ ;
            }
            if(!(r & 1)){
                if(mode == 0) res = min(res, ele[r]);
                else res = max(res, ele[r]);
                r -- ;
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

segtree L[N], R[N], U[N], D[N];
short Lf[N][N], Rf[N][N], Uf[N][N], Df[N][N];

bool is_valid(short i1, short j1, short i2, short j2){
    if(i1 == -1 || j1 == -1 || i2 == -1 || j2 == -1) return false;
    if(R[j1].get(i1 + 1, i2 - 1) < j2) return false;
    if(L[j2].get(i1 + 1, i2 - 1) > j1) return false;
    if(D[i1].get(j1 + 1, j2 - 1) < i2) return false;
    if(U[i2].get(j1 + 1, j2 - 1) > i1) return false;
    return true;
}

ll count_rectangles(vector<vector<int>> e){
    int n = e.size();
    int m = e[0].size();
    vector<int> mono;
    for(int i = 0 ; i < m ; i ++ ){
        L[i].init(n,1);
        R[i].init(n,0);
    }
    for(int i = 0 ; i < n; i ++ ){
        mono.clear();
        for(int j = 0 ; j < m ; j ++ ){
            Lf[i][j] = -1;
            while(!mono.empty() && e[i][mono.back()] <= e[i][j]){
                if(e[i][mono.back()] == e[i][j]){
                    L[j].upd(i, mono.back());
                }
                mono.pop_back();
            }
            if(!mono.empty()){
                Lf[i][j] = mono.back();
                L[j].upd(i, mono.back());
            }
            mono.push_back(j);
        }
        mono.clear();
        for(int j = m - 1; j >= 0 ; j -- ){
            Rf[i][j] = -1;
            while(!mono.empty() && e[i][mono.back()] <= e[i][j]){
                if(e[i][mono.back()] == e[i][j]){
                    R[j].upd(i, mono.back());
                }
                mono.pop_back();
            }
            if(!mono.empty()){
                Rf[i][j] = mono.back();
                R[j].upd(i, mono.back());
            }
            mono.push_back(j);
        }
    }
    for(int i = 0 ; i < n; i ++ ){
        U[i].init(m, 1);
        D[i].init(m, 0);
    }
    for(int j = 0 ; j < m ; j ++ ){
        mono.clear();
        for(int i = 0 ; i < n; i ++ ){
            Uf[i][j] = -1;
            while(!mono.empty() && e[mono.back()][j] <= e[i][j]){
                if(e[mono.back()][j] == e[i][j]){
                    U[i].upd(j, mono.back());
                }
                mono.pop_back();
            }
            if(!mono.empty()){
                Uf[i][j] = mono.back();
                U[i].upd(j, mono.back());
            }
            mono.push_back(i);
        }
        mono.clear();
        for(int i = n - 1; i >= 0 ; i -- ){
            Df[i][j] = -1;
            while(!mono.empty() && e[mono.back()][j] <= e[i][j]){
                if(e[mono.back()][j] == e[i][j]){
                    D[i].upd(j, mono.back());
                }
                mono.pop_back();
            }
            if(!mono.empty()){
                Df[i][j] = mono.back();
                D[i].upd(j, mono.back());
            }
            mono.push_back(i);
        }
    }
    vector<pair<pii, pii>> rect;
    for(int i = 1; i + 1 < n; i ++ ){
        for(int j = 1; j + 1 < m ; j ++ ){
            if(Uf[i][j] == -1 || Lf[i][j] ==-1 || Df[i][j] == -1 || Rf[i][j] == -1) continue;
            rect.push_back({mp(Uf[i][j], Lf[i][j]), mp(Df[i][j], Rf[i][j])});
        }
    }
    sort(rect.begin(), rect.end());
    rect.resize(unique(rect.begin(), rect.end()) - rect.begin());
    int ret = 0;
    for(auto x : rect){
        ret += is_valid(x.fi.fi, x.fi.se, x.se.fi, x.se.se);
    }
    return ret;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28