oj.uz

Submission #1059415

# Submission time Handle Problem Language Result Execution time Memory
1059415 2024-08-14T23:37:15 Z efishel Rectangles (IOI19_rect) C++17
0 / 100
 5000 ms 548188 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 3 ms 2364 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2292 KB Output is correct
6 Correct 2 ms 2400 KB Output is correct
7 Incorrect 2 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 3 ms 2364 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2292 KB Output is correct
6 Correct 2 ms 2400 KB Output is correct
7 Incorrect 2 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 3 ms 2364 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2292 KB Output is correct
6 Correct 2 ms 2400 KB Output is correct
7 Incorrect 2 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 3 ms 2364 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2292 KB Output is correct
6 Correct 2 ms 2400 KB Output is correct
7 Incorrect 2 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3106 ms 261712 KB Output is correct
2 Correct 2122 ms 205428 KB Output is correct
3 Correct 2984 ms 261832 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Incorrect 3083 ms 261928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 4869 ms 359172 KB Output is correct
3 Execution timed out 5063 ms 548188 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 3 ms 2364 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2292 KB Output is correct
6 Correct 2 ms 2400 KB Output is correct
7 Incorrect 2 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -