Submission #1030858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030858		Zicrus	Rectangles (IOI19_rect)	C++17	10 / 100	142 ms	612 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;

typedef long long ll;

ll m;
ll pow2;
vector<ll> seg;

ll segMax(ll low, ll high) {
    low += pow2; high += pow2;
    ll mx = 0;
    while (low <= high) {
        if (low & 1) mx = max(mx, seg[low++]);
        if (!(high & 1)) mx = max(mx, seg[high--]);
        low /= 2; high /= 2;
    }
    return mx;
}

ll count_rectangles(vector<vector<int>> a) {
    if (a.size() <= 2) return 0;
    m = a[0].size();
    pow2 = 1ll << (ll)ceil(log2(m));
    vector<int> am = a[1];
    seg = vector<ll>(2*pow2);
    for (int i = 0; i < m; i++) {
        seg[pow2+i] = (a[0][i] > am[i] && a[2][i] > am[i]) ? am[i] : 7000001;
    }
    for (int i = pow2-1; i > 0; i--) {
        seg[i] = max(seg[2*i], seg[2*i+1]);
    }

    ll res = 0;
    for (int i = 1; i < m-1; i++) {
        for (int j = i; j < m-1; j++) {
            ll border = min(am[i-1], am[j+1]);
            if (border > segMax(i, j)) res++;
        }
    }
    return res;
}

• 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