oj.uz

Submission #1030858

# Submission time Handle Problem Language Result Execution time Memory
1030858 2024-07-22T10:52:30 Z Zicrus Rectangles (IOI19_rect) C++17
10 / 100
 142 ms 612 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 604 KB Output is correct
2 Correct 100 ms 604 KB Output is correct
3 Correct 137 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 142 ms 612 KB Output is correct
6 Correct 141 ms 600 KB Output is correct
7 Correct 141 ms 604 KB Output is correct
8 Correct 138 ms 360 KB Output is correct
9 Correct 141 ms 604 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -