oj.uz

Submission #991423

# Submission time Handle Problem Language Result Execution time Memory
991423 2024-06-02T08:56:02 Z MarwenElarbi Rectangles (IOI19_rect) C++17
10 / 100
 355 ms 856 KB 
#include<bits/stdc++.h>
#include <cstdio>
#include <unistd.h>
#include <cassert>
#include <string>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=2505;
int segtree[nax*4];
vector<vector<int>> grid;
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos]=grid[1][l];
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
}
int query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return -1e9;
    if(l>=left&&r<=right) return segtree[pos];
    int mid=(r+l)/2;
    return max(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
long long count_rectangles(std::vector<std::vector<int> > a) {
    grid=a;
    int n=a.size();
    if(n<=2){
        return 0;
    }
    int m=a[0].size();
    int ans=0;
    int tab[m];
    for (int i = 0; i < m; ++i)
    {
        if(grid[1][i]>=grid[0][i]||grid[1][i]>=grid[2][i]) tab[i]=true;
        else tab[i]=0;
    }
    build(0,0,m-1);
    for (int i = 1; i < m-1; ++i)
    {
        if(tab[i]==1) continue;
        for (int j = i; j < m-1; ++j)
        {
            if(tab[j]==1) break;
            int cur=query(0,0,m-1,i,j);
            if(cur>=a[1][i-1]||cur>=a[1][j+1]) continue;
            ans++;
        }
    }
    return ans;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 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 355 ms 548 KB Output is correct
2 Correct 240 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 476 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

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