Submission #1255977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255977		nerrrmin	Rectangles (IOI19_rect)	C++20	10 / 100	4 ms	328 KiB

rect

#include "rect.h"
#define pb push_back
using namespace std;
const int maxn = 3e3 + 10;
int n, m;

int is[maxn], pref[maxn];

int arr[maxn];

//int t[maxn * 4];

/*void build(int i, int l, int r)
{
    if(l == r)
    {
        t[i] = arr[l];
        return;
    }
    int mid = (l + r)/2;
    build(2*i, l, mid);
    build(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
}

int ql, qr;
int query(int i, int l, int r)
{
    if(qr < l || ql > r)return 0;
    if(ql <= l && r <= qr)return t[i];
    int mid = (l + r)/2;
    return max(query(2*i, l, mid), query(2*i+1, mid+1, r));
}*/
long long count_rectangles(std::vector<std::vector<int> > a)
{
    n = a.size();
    m = a[0].size();
    if(n < 3)return 0;
    if(m < 3)return 0;
    for (int i = 0; i < m; ++ i)
    {
        arr[i] = a[1][i];
    }

   // build(1, 1, m-2);
    for (int i = 0; i < m; ++ i)
    {
        if(a[1][i] < a[0][i] && a[1][i] < a[2][i])is[i] = 1;
    }
    for (int i = 1; i < m; ++ i)
        pref[i] = pref[i-1] + is[i];
    int ans = 0;
    for (int lt = 1; lt < m-1; ++ lt)
    {

        int mx = 0;
        for (int rt = lt; rt < m-1; ++ rt)
        {
            mx = max(mx, arr[rt]);
            int onl = lt - 1;
            int onr = rt + 1;

            int cntis = pref[rt] - pref[lt-1];
            if(cntis == rt - lt + 1 && mx < min(a[1][onl], a[1][onr]))
                ans ++;
        }
    }
	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