Submission #351049

#	Time	Username	Problem	Language	Result	Execution time	Memory
351049		qwerasdfzxcl	Rectangles (IOI19_rect)	C++14	10 / 100	106 ms	150252 KiB

rect

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int matrix[2525][2525];
vector<int> pos[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 div1idx(int s, int e, int idx){
    if (e-s==1){
        if (matrix[idx][s]<matrix[idx][s+1] && matrix[idx][s]<matrix[idx][s-1] && matrix[idx][s]<min(matrix[idx-1][s], matrix[idx+1][s])) return 1;
        return 0;
    }
    ll ret=div1idx(s, (s+e)/2, idx)+div1idx((s+e)/2, e, idx);
    int x=(s+e)/2-1, y=(s+e)/2, cur;
    cur=max(matrix[idx][x], matrix[idx][y]);
    bool tmp1=(matrix[idx][x]<min(matrix[idx-1][x], matrix[idx+1][x]))&&(matrix[idx][y]<min(matrix[idx-1][y], matrix[idx+1][y]));
    while(x>s && y<e-1){
        if (!tmp1) return ret;
        if (cur<matrix[idx][x-1] && cur<matrix[idx][y+1]) ret++;
        if (matrix[idx][x-1]<matrix[idx][y+1]){
            cur=max(cur, matrix[idx][--x]);
            tmp1=matrix[idx][x]<min(matrix[idx-1][x], matrix[idx+1][x]);
        }
        else{
            cur=max(cur, matrix[idx][++y]);
            tmp1=matrix[idx][y]<min(matrix[idx-1][y], matrix[idx+1][y]);
        }
    }
    if (x==s){
        for (;y<=e-1;cur=max(cur, matrix[idx][y])){
            if (!tmp1) return ret;
            if(cur<matrix[idx][x-1] && cur<matrix[idx][y+1]) ret++;
            y++;
            tmp1=matrix[idx][y]<min(matrix[idx-1][y], matrix[idx+1][y]);
        }
    }
    else{
        for (;x>=s;cur=max(cur, matrix[idx][x])){
            if (!tmp1) return ret;
            if(cur<matrix[idx][x-1] && cur<matrix[idx][y+1]) ret++;
            x--;
            tmp1=matrix[idx][x]<min(matrix[idx-1][x], matrix[idx+1][x]);
        }
    }
    return ret;
}*/

ll div1idxrev(int s, int e, int idx){
    //printf("%d %d\n", s, e);
    if (e-s==1){
        if (matrix[s][idx]<matrix[s+1][idx] && matrix[s][idx]<matrix[s-1][idx] && matrix[s][idx]<min(matrix[s][idx-1], matrix[s][idx+1])) return 1;
        return 0;
    }
    ll ret=div1idxrev(s, (s+e)/2, idx)+div1idxrev((s+e)/2, e, idx);
    int x=(s+e)/2-1, y=(s+e)/2, cur;
    cur=max(matrix[x][idx], matrix[y][idx]);
    bool tmp1=(matrix[x][idx]<min(matrix[x][idx-1], matrix[x][idx+1]))&&(matrix[y][idx]<min(matrix[y][idx-1], matrix[y][idx+1]));
    while(x>s && y<e-1){
        if (!tmp1) return ret;
        if (cur<matrix[x-1][idx] && cur<matrix[y+1][idx]) ret++;
        if (matrix[x-1][idx]<matrix[y+1][idx]){
            cur=max(cur, matrix[--x][idx]);
            tmp1=matrix[x][idx]<min(matrix[x][idx-1], matrix[x][idx+1]);
        }
        else{
            cur=max(cur, matrix[++y][idx]);
            tmp1=matrix[y][idx]<min(matrix[y][idx-1], matrix[y][idx+1]);
        }
    }
    if (x==s){
        for (;y<=e-1;cur=max(cur, matrix[y][idx])){
            if (!tmp1) return ret;
            if(cur<matrix[x-1][idx] && cur<matrix[y+1][idx]) ret++;
            y++;
            tmp1=matrix[y][idx]<min(matrix[y][idx-1], matrix[y][idx+1]);
        }
    }
    else{
        for (;x>=s;cur=max(cur, matrix[x][idx])){
            if (!tmp1) return ret;
            if(cur<matrix[x-1][idx] && cur<matrix[y+1][idx]) ret++;
            x--;
            tmp1=matrix[x][idx]<min(matrix[x][idx-1], matrix[x][idx+1]);
        }
    }
    return ret;
}

ll div3(int s, int e, int s0, int e0){
    //printf("%d %d\n", s, e);
    int m=(s+e)/2, m0=(s0+e0)/2;
    //printf("%d %d\n", s, e);
    int curpossum[2525]={0}, curmax[2525];
    vector<int> cur2[2525], tmp[2525];
    int x1=m-1, x2=m;
    if (e-s==1){
        ll ret=0;
        for (int i=s0;i<e0;i++){
            if (matrix[s][i]<matrix[s-1][i] && matrix[s][i]<matrix[s+1][i]){
                curpossum[i+1]=curpossum[i]+1;
            }
            else curpossum[i+1]=curpossum[i];
        }
        for (int i=s0;i<m0;i++){
            for (int j:pos[s][i]){
                if (curpossum[j+1]-curpossum[i]==(j+1-i)) ret++;
            }
        }
        //printf("div3: %d %d %lld\n", s, e, ret);
        return ret;
    }
    ll ret=div3(s, m, s0, e0)+div3(m, e, s0, e0);
    for (int i=s0;i<e0;i++){
        //curpos, curmax init
        curmax[i]=max(matrix[x1][i], matrix[x2][i]);
        if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
            curpossum[i+1]=curpossum[i]+1;
        }
        else{
            curpossum[i+1]=curpossum[i];
        }
    }
    for (int i=s0;i<m0;i++){
        //cur2 init;
        int j1=0, j2=0;
        while(j1<pos[x1][i].size() && j2<pos[x2][i].size()){
            if (pos[x1][i][j1]==pos[x2][i][j2]){
                cur2[i].push_back(pos[x1][i][j1]);
                if (curpossum[cur2[i].back()+1]-curpossum[i]==(cur2[i].back()-i+1)) ret++;
                j1++;
            }
            else if (pos[x1][i][j1]<pos[x2][i][j2]) j1++;
            else j2++;
        }
    }
    while(x1>s && x2<e-1){
        if (matrix[x1-1][m0]<matrix[x2+1][m0] || (matrix[x1-1][m0]==matrix[x2+1][m0] && matrix[x1-1][m0-1]<matrix[x2+1][m0-1])){
            x1--;
            for (int i=s0;i<e0;i++){
                curmax[i]=max(curmax[i], matrix[x1][i]);
                if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
                    curpossum[i+1]=curpossum[i]+1;
                }
                else{
                    curpossum[i+1]=curpossum[i];
                }
            }
            for (int i=s0;i<m0;i++){
                tmp[i].clear();
                int j1=0, j2=0;
                while(j1<cur2[i].size() && j2<pos[x1][i].size()){
                    if (cur2[i][j1]==pos[x1][i][j2]){
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++;
                    }
                    else if (cur2[i][j1]<pos[x1][i][j2]) j1++;
                    else j2++;
                }
                cur2[i].clear();
                for (int t:tmp[i]) cur2[i].push_back(t);
            }
        }
        else{
            x2++;
            for (int i=s0;i<e0;i++){
                curmax[i]=max(curmax[i], matrix[x2][i]);
                if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
                    curpossum[i+1]=curpossum[i]+1;
                }
                else{
                    curpossum[i+1]=curpossum[i];
                }
            }
            for (int i=s0;i<m0;i++){
                tmp[i].clear();
                int j1=0, j2=0;
                while(j1<cur2[i].size() && j2<pos[x2][i].size()){
                    if (cur2[i][j1]==pos[x2][i][j2]){
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++;
                    }
                    else if (cur2[i][j1]<pos[x2][i][j2]) j1++;
                    else j2++;
                }
                cur2[i].clear();
                for (int t:tmp[i]) cur2[i].push_back(t);
            }
        }
    }
    if (x1==s){
        x2++;
        for (;x2<=e-1;x2++){
            for (int i=s0;i<e0;i++){
                curmax[i]=max(curmax[i], matrix[x2][i]);
                if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
                    curpossum[i+1]=curpossum[i]+1;
                }
                else{
                    curpossum[i+1]=curpossum[i];
                }
            }
            for (int i=s0;i<m0;i++){
                tmp[i].clear();
                int j1=0, j2=0;
                while(j1<cur2[i].size() && j2<pos[x2][i].size()){
                    if (cur2[i][j1]==pos[x2][i][j2]){
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++;
                    }
                    else if (cur2[i][j1]<pos[x2][i][j2]) j1++;
                    else j2++;
                }
                cur2[i].clear();
                for (int t:tmp[i]) cur2[i].push_back(t);
            }
        }
    }
    else{
        x1--;
        for (;x1>=s;x1--){
            for (int i=s0;i<e0;i++){
                curmax[i]=max(curmax[i], matrix[x1][i]);
                if (curmax[i]<matrix[x1-1][i] && curmax[i]<matrix[x2+1][i]){
                    curpossum[i+1]=curpossum[i]+1;
                }
                else{
                    curpossum[i+1]=curpossum[i];
                }
            }
            for (int i=s0;i<m0;i++){
                tmp[i].clear();
                int j1=0, j2=0;
                while(j1<cur2[i].size() && j2<pos[x1][i].size()){
                    if (cur2[i][j1]==pos[x1][i][j2]){
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++;
                    }
                    else if (cur2[i][j1]<pos[x1][i][j2]) j1++;
                    else j2++;
                }
                cur2[i].clear();
                for (int t:tmp[i]) cur2[i].push_back(t);
            }
        }
    }
    //if (s==1 && e==4) printf("%d %d %d\n", (int)cur2[1].size(), curpossum[4], curpossum[1]);
    //printf("div3: %d %d %lld\n", s, e, ret);
    return ret;
}

ll div2(int s, int e){
    //printf("%d %d\n", s, e);
    if (e-s==1){
        //printf("%d %d\n", s, e);
        //printf("%d %d %lld\n", s, e, div1idxrev(1, n-1, s));
        return div1idxrev(1, n-1, s);
    }
    int m=(s+e)/2;
    ll ret=div2(s, m)+div2(m, e);
    for (int i=0;i<n;i++){
        for (int j=s;j<e;j++) pos[i][j].clear();
        int x1=m-1, x2=m, cur1=max(matrix[i][x1], matrix[i][x2]);
        while(x1>s && x2<e-1){
            if (cur1<matrix[i][x1-1] && cur1<matrix[i][x2+1]) pos[i][x1].push_back(x2);
            if (matrix[i][x1-1]<matrix[i][x2+1]) cur1=max(cur1, matrix[i][--x1]);
            else cur1=max(cur1, matrix[i][++x2]);
        }
        if (x1==s){
            for (;x2<=e-1;cur1=max(cur1, matrix[i][++x2])) if (cur1<matrix[i][x1-1] && cur1<matrix[i][x2+1]) pos[i][x1].push_back(x2);
        }
        else{
            for (;x1>=s;cur1=max(cur1, matrix[i][--x1])) if (cur1<matrix[i][x1-1] && cur1<matrix[i][x2+1]) pos[i][x1].push_back(x2);
        }
    }
    ret += div3(1, n-1, s, e);
    //printf("%d %d\n", s, e);
    //printf("%d %d %lld\n", s, e, ret);
    return ret;
}

ll solve1(){
    if (n<=2){
        //printf("0\n");
        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);
    //printf("%lld\n", ret);
    return ret;
}

ll count_rectangles(vector<vector<int>> a){
    /*scanf("%d %d", &n, &M);*/
  	n=a.size(), M=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();
    else if (M<=2) return 0;
    //printf("%lld\n", div1idxrev(1, 2, 3));
    return solve1();
}

Compilation message (stderr)

rect.cpp: In function 'll div3(int, int, int, int)':
rect.cpp:149:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         while(j1<pos[x1][i].size() && j2<pos[x2][i].size()){
      |               ~~^~~~~~~~~~~~~~~~~~
rect.cpp:149:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         while(j1<pos[x1][i].size() && j2<pos[x2][i].size()){
      |                                       ~~^~~~~~~~~~~~~~~~~~
rect.cpp:174:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |                 while(j1<cur2[i].size() && j2<pos[x1][i].size()){
      |                       ~~^~~~~~~~~~~~~~~
rect.cpp:174:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |                 while(j1<cur2[i].size() && j2<pos[x1][i].size()){
      |                                            ~~^~~~~~~~~~~~~~~~~~
rect.cpp:201:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |                 while(j1<cur2[i].size() && j2<pos[x2][i].size()){
      |                       ~~^~~~~~~~~~~~~~~
rect.cpp:201:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |                 while(j1<cur2[i].size() && j2<pos[x2][i].size()){
      |                                            ~~^~~~~~~~~~~~~~~~~~
rect.cpp:230:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |                 while(j1<cur2[i].size() && j2<pos[x2][i].size()){
      |                       ~~^~~~~~~~~~~~~~~
rect.cpp:230:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |                 while(j1<cur2[i].size() && j2<pos[x2][i].size()){
      |                                            ~~^~~~~~~~~~~~~~~~~~
rect.cpp:259:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |                 while(j1<cur2[i].size() && j2<pos[x1][i].size()){
      |                       ~~^~~~~~~~~~~~~~~
rect.cpp:259:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |                 while(j1<cur2[i].size() && j2<pos[x1][i].size()){
      |                                            ~~^~~~~~~~~~~~~~~~~~

• 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