제출 #296633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296633		Osama_Alkhodairy	Rectangles (IOI19_rect)	C++17	100 / 100	3832 ms	856724 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long

const int N = 2501;
const int INF = (int)1e9;

struct segment{
    vector <int> tree;
    int n;
    void build(vector <int> &a, int b){
        n = a.size();
        tree.resize(2 * n, -INF);
        for(int i = 0 ; i < n ; i++){
            if(a[i] != -1) tree[i + n] = a[i] * b;
        }
        for(int i = n - 1 ; i > 0 ; i--){
            tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
        }
    }
    int query(int l, int r){
        r++;
        int ret = -INF;
        for(l += n, r += n ; l < r ; l >>= 1, r >>= 1){
            if(l & 1) ret = max(ret, tree[l++]);
            if(r & 1) ret = max(ret, tree[--r]);
        }
        return ret;
    }
};

int n, m, vis[N * N];
vector <vector <int> > a;
vector <vector <int> > us, rs, ds, ls, ue, re, de, le;
vector <segment> ue_tree, re_tree, de_tree, le_tree;
vector <int> v[N * N];

vector <int> calc(vector <int> &a, int b, int c){
    //~ b = 0 for >
    //~ b = 1 for >=
    //~ c = 0 for forward
    //~ c = 1 for backward
    int n = a.size();
    vector <int> inds;
    for(int i = 0 ; i < n ; i++){
        if(c == 0) inds.push_back(i);
        else inds.push_back(n - i - 1);
    }
    vector <int> ret(n);
    vector <int> cur;
    for(auto &i : inds){
        while(cur.size() && a[i] >= a[cur.back()] + b){
            cur.pop_back();
        }
        if(cur.size() == 0) ret[i] = -1;
        else ret[i] = cur.back();
        cur.push_back(i);
    }
    return ret;
}
void add(int r1, int c1, int r2, int c2){
    if(r1 == -1 || c1 == -1 || r2 == -1 || c2 == -1) return;
    v[r1 * m + c1].push_back(r2 * m + c2);
}
bool check(int r1, int c1, int r2, int c2){
    int v = -de_tree[r1].query(c1 + 1, c2 - 1);
    if(v < r2) return 0;
    v = ue_tree[r2].query(c1 + 1, c2 - 1);
    if(v > r1) return 0;
    v = -re_tree[c1].query(r1 + 1, r2 - 1);
    if(v < c2) return 0;
    v = le_tree[c2].query(r1 + 1, r2 - 1);
    if(v > c1) return 0;
    return 1;
}
long long count_rectangles(std::vector<std::vector<int> > A) {
    a = A;
    n = a.size();
    m = a[0].size();
    us.resize(n, vector <int>(m));
    ue.resize(n, vector <int>(m));
    ds.resize(n, vector <int>(m));
    de.resize(n, vector <int>(m));
    ls.resize(n, vector <int>(m));
    le.resize(n, vector <int>(m));
    rs.resize(n, vector <int>(m));
    re.resize(n, vector <int>(m));
    ue_tree.resize(n);
    de_tree.resize(n);
    le_tree.resize(m);
    re_tree.resize(m);
    for(int i = 0 ; i < n ; i++){
        vector <int> cur = a[i];
        ls[i] = calc(cur, 0, 0);
        le[i] = calc(cur, 1, 0);
        rs[i] = calc(cur, 0, 1);
        re[i] = calc(cur, 1, 1);
    }
    for(int j = 0 ; j < m ; j++){
        vector <int> cur(n);
        for(int i = 0 ; i < n ; i++){
            cur[i] = a[i][j];
        }
        vector <int> g;
        g = calc(cur, 0, 0);
        for(int i = 0 ; i < n ; i++){
            us[i][j] = g[i];
        }
        g = calc(cur, 1, 0);
        for(int i = 0 ; i < n ; i++){
            ue[i][j] = g[i];
        }
        g = calc(cur, 0, 1);
        for(int i = 0 ; i < n ; i++){
            ds[i][j] = g[i];
        }
        g = calc(cur, 1, 1);
        for(int i = 0 ; i < n ; i++){
            de[i][j] = g[i];
        }
    }
    for(int i = 0 ; i < n ; i++){
        ue_tree[i].build(ue[i], 1);
        de_tree[i].build(de[i], -1);
    }
    for(int j = 0 ; j < m ; j++){
        vector <int> cur(n);
        for(int i = 0 ; i < n ; i++){
            cur[i] = le[i][j];
        }
        le_tree[j].build(cur, 1);
        cur.assign(n, 0);
        for(int i = 0 ; i < n ; i++){
            cur[i] = re[i][j];
        }
        re_tree[j].build(cur, -1);
    }
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            add(us[i][j], ls[i][j], ds[i][j], rs[i][j]);
        }
    }
    int ret = 0;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            for(auto &k : v[i * m + j]){
                if(vis[k]) continue;
                vis[k] = 1;
                ret += check(i, j, k / m, k % m);
            }
            for(auto &k : v[i * m + j]){
                vis[k] = 0;
            }
        }
    }
    return ret;
}

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