Submission #267173

#	Time	Username	Problem	Language	Result	Execution time	Memory
267173		doowey	Rectangles (IOI19_rect)	C++14	59 / 100	5044 ms	341948 KiB

rect

#pragma GCC optimize("Ofast")
#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 int N = 2505;

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

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

bool is_valid(int i1, int j1, int i2, int 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]){
                mono.pop_back();
            }
            if(!mono.empty())
                Lf[i][j] = mono.back();
            mono.push_back(j);
        }
        mono.clear();
        for(int j = 0; j < m ; j ++ ){
            while(!mono.empty() && e[i][mono.back()] < e[i][j]){
                mono.pop_back();
            }
            if(mono.empty()){
                L[j].upd(i, -1);
            }
            else{
                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]){
                mono.pop_back();
            }
            if(!mono.empty())
                Rf[i][j] = mono.back();
            mono.push_back(j);
        }
        mono.clear();
        for(int j = m - 1; j >= 0;  j -- ){
            while(!mono.empty() && e[i][mono.back()] < e[i][j]){
                mono.pop_back();
            }
            if(mono.empty())
                R[j].upd(i, 5000);
            else
                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]){
                mono.pop_back();
            }
            if(!mono.empty())
                Uf[i][j] = mono.back();
            mono.push_back(i);
        }
        mono.clear();
        for(int i = 0 ; i < n; i ++ ){
            while(!mono.empty() && e[mono.back()][j] < e[i][j])
                mono.pop_back();
            if(mono.empty())
                U[i].upd(j, -1);
            else
                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])
                mono.pop_back();
            if(!mono.empty())
                Df[i][j] = mono.back();
            mono.push_back(i);
        }
        mono.clear();
        for(int i = n - 1; i >= 0 ; i -- ){
            while(!mono.empty() && e[mono.back()][j] < e[i][j])
                mono.pop_back();
            if(mono.empty())
                D[i].upd(j, 5000);
            else
                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(is_valid(Uf[i][j], Lf[i][j], Df[i][j], Rf[i][j]))
                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());
    return rect.size();
}

• 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