Submission #144527

#	Time	Username	Problem	Language	Result	Execution time	Memory
144527		shdut	Rectangles (IOI19_rect)	C++14	10 / 100	5123 ms	846592 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 2505
#define pb push_back
#define x first
#define y second
#define ls p<<1
#define rs p<<1|1
#define vi std::vector<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];
vi H[N][N], W[N][N];
unordered_map<int,int>g[N][N];
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)rep(j, 0, m)W[i][j].clear();
    rep(i, 0, n)rep(j, 0, n)H[i][j].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];
                W[k][j].pb(i);
                //cerr << q[t-1] << " " << j << " " << i << " ..\n";
            }
            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(W[k][q[t-1]].empty() || W[k][q[t-1]].back() != i){
                    W[k][q[t-1]].pb(i);
                    //cerr << j << " " << q[t-1] << " " <<  i << " ..\n";
                }
            }
            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];
                H[k][i].pb(j);
                //cerr << q[t-1] << " " << i << " " << j << " ,,\n";
            }
            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(H[k][q[t-1]].empty() || H[k][q[t-1]].back() != j){
                    H[k][q[t-1]].pb(j);
                    //cerr << i << " " << q[t-1] << " " <<  j << " ,,\n";
                }
            }
            q[t++] = i;
        }
    }
    rep(i, 2, 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][j+1]), i-1) - lower_bound(all(W[w][j+1]), i-h+1);
            if(y < h-1)continue;
            int x = upper_bound(all(H[h][i]), j) - lower_bound(all(H[h][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;
            if(g[x][y].count(id) == 0){
                g[x][y][id] = 1;
                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;
    rep(i, 0, n)rep(j, 0, m)g[i][j].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