제출 #991507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991507		MarwenElarbi	Rectangles (IOI19_rect)	C++17	37 / 100	5046 ms	34140 KiB

rect

#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();
    if(m<=2) return 0;
    int ans=0;
    for (int i = 1; i < n-1; ++i)
    {
        for (int j = 1; j < m-1; ++j)
        {
            for (int k = i; k < n-1; ++k)
            {
                for (int t = j; t < m-1; ++t)
                {
                    bool test=true;
                    for (int x = i; x <= k; ++x)
                    {
                        for (int y = j; y <= t; ++y)
                        {
                            if(grid[x][y]>=grid[x][j-1]) test=false;
                            else if(grid[x][y]>=grid[x][t+1]) test=false;
                            else if(grid[x][y]>=grid[i-1][y]) test=false;
                            else if(grid[x][y]>=grid[k+1][y]) test=false;
                            if(!test) break;
                        }
                        if(!test) break;
                    }
                    ans+=test;
                }
            }
        }
    }
    return ans;
}

class InputReader {
private:
    static const int SIZE = 4096;
    
    int inputFileDescriptor;
    char buf[SIZE];
    int curChar;
    int numChars;

public:

    inline InputReader(int _inputFileDescriptor):
        inputFileDescriptor(_inputFileDescriptor),
        curChar(0),
        numChars(0) {
    }

    inline void close() {
        ::close(inputFileDescriptor);
    }

    inline char read() {
        assert(numChars != -1);
        if (curChar >= numChars) {
            curChar = 0;
            numChars = ::read(inputFileDescriptor, buf, SIZE);
            if (numChars == -1)
                return -1;
        }
        return buf[curChar++];
    }

    inline int readInt() {
        int c = eatWhite();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            assert(c >= '0' && c <= '9');
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    inline string readString() {
        char c = eatWhite();
        string res;
        do {
            res += c;
            c = read();
        } while (!isSpaceChar(c));
        return res;
    }

    inline string readLine() {
        string res;
        while (true) {
            char c = read();
            if (c == '\n' || c == '\r' || c == -1)
                break;
            res += c;
        }
        return res;
    }

    inline char eatWhite() {
        char c = read();
        while (isSpaceChar(c)) 
            c = read();
        return c;
    }

    static inline bool isSpaceChar(char c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
};

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28