Submission #144548

#	Time	Username	Problem	Language	Result	Execution time	Memory
144548		shdut	Rectangles (IOI19_rect)	C++14	10 / 100	5020 ms	164840 KiB

rect

#include "rect.h"
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;

#define inf 1000000007
#define SZ(x) x.size()
#define all(x) x.begin(), x.end()
#define N 2501
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define ls p<<1
#define rs p<<1|1
#define vi std::vector<int>
#define pii pair<int,int>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b - 1; i >= a; i--)
#define DBG(x) cerr << (#x) << "=" << x << "\n";

int U[N][N], L[N][N], q[N];
vector<pii> H[N], W[N];
set<pii> g;
int solve(std::vector<std::vector<int> > &a, int f1 = 0, int f2 = 0){
    int ans = 0;
    int n = SZ(a), m = SZ(a[0]), k;
    //for(auto &o : a){
    //    for(auto &x : o)cerr << x << " ";
    //    cerr << "\n";
    //}
    rep(i, 0, m)W[i].clear();
    rep(i, 0, n)H[i].clear();
    rep(i, 0, n){
        int t = 0;
        rep(j, 0, m){
            while(t && a[i][q[t-1]] < a[i][j])t--;
            L[i][j] = t == 0 ? -1 : q[t-1];
            if(t){
                k = j - q[t-1];
                if(k >= 2)W[k].pb({j, i});
            }
            q[t++] = j;
        }
        t = 0;
        per(j, 0, m){
            while(t && a[i][q[t-1]] < a[i][j])t--;
            if(t){
                k = q[t-1] - j;
                if(k >= 2)W[k].pb({q[t-1], i});
            }
            q[t++] = j;
        }
    }
    rep(j, 0, m){
        int t = 0;
        rep(i, 0, n){
            while(t && a[q[t-1]][j] < a[i][j])t--;
            U[i][j] = t == 0 ? -1 : q[t-1];
            if(t){
                k = i - q[t-1];
                if(k >=2 )H[k].pb({i, j});
            }
            q[t++] = i;
        }
        t = 0;
        per(i, 0, n){
            while(t && a[q[t-1]][j] < a[i][j])t--;
            if(t){
                k = q[t-1] - i;
                if(k >= 2)H[k].pb({q[t-1], j});
            }
            q[t++] = i;
        }
    }
    rep(i, 2, n){
        sort(all(H[i]));
        H[i].erase(unique(all(H[i])), H[i].end());
    }
    rep(i, 2, m){
        sort(all(W[i]));
        W[i].erase(unique(all(W[i])), W[i].end());
    }
    rep(i, 1, n){
        rep(j, 1, m-1){
            int w = L[i-1][j+1], h = U[i][j];
            if(w < 0 || h < 0)continue;
            w = j + 1 - w;
            h = i - h;
            if(w < 2 || h < 2)continue;
            int y = upper_bound(all(W[w]), mp(j+1, i-1)) - lower_bound(all(W[w]), mp(j+1,i-h+1));
            if(y < h-1)continue;
            int x = upper_bound(all(H[h]), mp(i, j)) - lower_bound(all(H[h]), mp(i, j-w+2));
            if(x < w-1)continue;
            x = i-h+1, y = j+1-w+1;
            if(f1)x = n-1-x;
            if(f2)y = m-1-y;
            int x1 = i-1, y1 = j;
            if(f1)x1 = n-1-x1;
            if(f2)y1 = m-1-y1;
            if(x1 > x)swap(x, x1);
            if(y1 > y)swap(y, y1);
            int id = x1 * m + y1;
            int id1 = x * m + y;
            if(g.find({id, id1}) == g.end()){
                g.insert({id, id1});
                ans++;
                //cerr << i << " " << j << "\n";
                //cerr << j+1-w+1 << " " << j << " , " << i-h+1 << " " << i-1 << "\n";
                //cerr << x1 << " " << y1 << ","  << x << " " << y << "\n";
            }
        }
    }
    //DBG(ans)
    return ans;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
    int n = SZ(a), m = SZ(a[0]);
    long long ans = 0;
    g.clear();
    rep(x, 0, 2){
        rep(y, 0, 2){
            ans += solve(a, x, y);
            rep(j, 0, m/2)rep(i, 0, n)swap(a[i][j], a[i][m-1-j]);
        }
        rep(i, 0, n/2)rep(j, 0, m)swap(a[i][j], a[n-1-i][j]);
    }
    return ans;
}

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