Submission #350985

#	Time	Username	Problem	Language	Result	Execution time	Memory
350985		qwerasdfzxcl	Rectangles (IOI19_rect)	C++14	10 / 100	1 ms	492 KiB

rect

#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;
int matrix[2525][2525];
int n, M;
 
ll div1(int s, int e){
    if (e-s==1){
        if (matrix[1][s]<matrix[1][s+1] && matrix[1][s]<matrix[1][s-1]) return 1;
        return 0;
    }
    ll ret=div1(s, (s+e)/2)+div1((s+e)/2, e);
    int x=(s+e)/2-1, y=(s+e)/2, cur;
    cur=max(matrix[1][x], matrix[1][y]);
    while(x>s && y<e-1){
        if (cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
        if (matrix[1][x-1]<matrix[1][y+1]) cur=max(cur, matrix[1][--x]);
        else cur=max(cur, matrix[1][++y]);
    }
    if (x==s){
        for (;y<=e-1;cur=max(cur, matrix[1][++y])) if(cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
    }
    else{
        for (;x>=s;cur=max(cur, matrix[1][--x])) if(cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
    }
    return ret;
}
 
ll solve1(){
    if (n<=2) return 0;
    vector<pair<int, int>> pi;
    int s=-2;
    for (int i=0;i<M;i++) if (!(matrix[1][i]<matrix[0][i] && matrix[1][i]<matrix[2][i])){
        if (s==-2){
            s=i+1; continue;
        }
        if (s!=i) pi.push_back(make_pair(s, i));
        s=i+1;
    }
    ll ret=0;
    for (auto p:pi) ret += div1(p.first, p.second);
    return ret;
}
 
ll count_rectangles(vector<vector<int>> a){
    n=(int)a.size();
  	M=(int)a[0].size();
    for (int i=0;i<n;i++){
        for (int j=0;j<M;j++) matrix[i][j]=a[i][j];
    }
    if (n<=3) return solve1();
    return 0;
}

• 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