Submission #350042

#	Time	Username	Problem	Language	Result	Execution time	Memory
350042		qwerasdfzxcl	Rectangles (IOI19_rect)	C++14	0 / 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]) x--;
        else y++;
    }
    if (x==s){
        for (;y<e-1;y++) if(cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
    }
    else{
        for (;x>s;x--) if(cur<matrix[1][x-1] && cur<matrix[1][y+1]) ret++;
    }
    return ret;
}

void solve1(){
    if (n<=2){
        printf("0\n");
        return;
    }
    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;
        }
        pi.push_back(make_pair(s, i));
        s=i+1;
    }
    ll ret=0;
    for (auto p:pi) ret += div1(p.first, p.second);
    printf("%lld\n", ret);
}

ll count_rectangles(vector<vector<int>> a){
    scanf("%d %d", &n, &m);
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++) scanf("%d", &matrix[i][j]);
    }
    if (n<=3) solve1();
    return 0;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
rect.cpp:52:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         for (int j=0;j<m;j++) scanf("%d", &matrix[i][j]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~

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