Submission #1059415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059415		efishel	Rectangles (IOI19_rect)	C++17	0 / 100	5063 ms	548188 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 1<<12;
const short INF = MAXN+16;
short gi1[MAXN][MAXN], gi2[MAXN][MAXN], gj1[MAXN][MAXN], gj2[MAXN][MAXN];

using dat = pair <pair <short, short>, pair <short, short> >;
dat operator+ (const dat &a, const dat &b) {
    return dat{
        { min(a.first.first, b.first.first),
        min(a.first.second, b.first.second) },
        { max(a.second.first, b.second.first),
        max(a.second.second, b.second.second) }
    };
}

const dat IDEM = { { INF, INF }, { -INF, -INF } };
const dat OVER = { { -INF, -INF }, { INF, INF } };
dat tree[2*MAXN][2*MAXN];
// dat st[2*MAXN][2*MAXN];

// void build(){
//     for(ll i=0;i<n;i++)for(ll j=0;j<m;j++)st[i+n][j+m]=a[i][j];
//     for(ll i=0;i<n;i++)for(int j=m-1;j;--j)
//         st[i+n][j]=(st[i+n][j<<1]+st[i+n][j<<1|1]);
//     for(int i=n-1;i;--i)for(ll j=0;j<2*m;j++)
//         st[i][j]=(st[i<<1][j]+st[i<<1|1][j]);
// }
void update(int x, int y, dat v){
    tree[x+MAXN][y+MAXN]=v;
    for(int j=y+MAXN;j>1;j>>=1)tree[x+MAXN][j>>1]=(tree[x+MAXN][j]+tree[x+MAXN][j^1]);
    for(int i=x+MAXN;i>1;i>>=1)for(int j=y+MAXN;j;j>>=1)
        tree[i>>1][j]=(tree[i][j]+tree[i^1][j]);
}
dat query(int x0, int x1, int y0, int y1){
    x1++; y1++;
    dat r=IDEM;
    for(int i0=x0+MAXN,i1=x1+MAXN;i0<i1;i0>>=1,i1>>=1){
        int t[4],q=0;
        if(i0&1)t[q++]=i0++;
        if(i1&1)t[q++]=--i1;
        for(ll k=0;k<q;k++)for(int j0=y0+MAXN,j1=y1+MAXN;j0<j1;j0>>=1,j1>>=1){
            if(j0&1)r=(r+tree[t[k]][j0++]);
            if(j1&1)r=(r+tree[t[k]][--j1]);
        }
    }
    return r;
}


ll count_rectangles (vector <vi> a) {
    ll n = a.size(), m = a[0].size();
    for (ll i = 0; i < n; i++) {
        vii stk;
        stk.push_back({ INF, -1 });
        for (ll j = 0; j < m; j++) {
            while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
            gj1[i][j] = stk.back().second+1;
            stk.push_back({ a[i][j], j });
        }
    }
    for (ll i = 0; i < n; i++) {
        vii stk;
        stk.push_back({ INF, m });
        for (ll j = m-1; j >= 0; j--) {
            while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
            gj2[i][j] = stk.back().second-1;
            stk.push_back({ a[i][j], j });
        }
    }
    for (ll j = 0; j < m; j++) {
        vii stk;
        stk.push_back({ INF, -1 });
        for (ll i = 0; i < n; i++) {
            while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
            gi1[i][j] = stk.back().second+1;
            stk.push_back({ a[i][j], i });
        }
    }
    for (ll j = 0; j < m; j++) {
        vii stk;
        stk.push_back({ INF, n });
        for (ll i = n-1; i >= 0; i--) {
            while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
            gi2[i][j] = stk.back().second-1;
            stk.push_back({ a[i][j], i });
        }
    }

    priority_queue <pair <ll, ii> > pq;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < m; j++) {
            pq.push({ -a[i][j], { i, j } });
        }
    }
    for (ll i1 = 0; i1 < max(n,m); i1++) {
        for (ll i2 = 0; i2 < max(n,m); i2++) {
            update(i1, i2, OVER);
        }
    }
    ll ans = 0;
    while (pq.size()) {
        auto [i, j] = pq.top().second; pq.pop();
        ll i1 = gi1[i][j];
        ll j1 = gj1[i][j];
        ll i2 = gi2[i][j];
        ll j2 = gj2[i][j];
        update(i, j, { { i1, j1 }, { i2, j2 } });
        // cerr << i << ' ' << j << "   ";
        // cerr << i1 << ' ' << j1 << ' ' << i2 << ' ' << j2 << '\n';
        auto s = query(i1, i2, j1, j2);
        auto [p1,p2]=s;
        auto [p3,p4]=p1;
        auto [p5,p6]=p2;
        // cerr << p3 << ' '<< p4 << ' ' << p5 << ' ' << p6 << '\n';
        if (s == dat{ { i1, j1 }, { i2, j2 } } && 0 < i1 && i2 < n-1 && 0 < j1 && j2 < m-1) ans++;
    }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:120:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  120 |         auto [p3,p4]=p1;
      |              ^~~~~~~
rect.cpp:121:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  121 |         auto [p5,p6]=p2;
      |              ^~~~~~~

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