제출 #415498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415498		qwerasdfzxcl	Rectangles (IOI19_rect)	C++14	100 / 100	4968 ms	442684 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

typedef long long ll;
using namespace std;
vector<int> pos[2525][2525];
int n, M;
int curpossum[2525], curmax[2525];
vector<int> cur2[2525], tmp[2525];

ll div1(int s, int e, vector<vector<int>> &matrix){
    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, matrix)+div1((s+e)/2, e, matrix);
    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 div1idxrev(int s, int e, int idx, vector<vector<int>> &matrix){
    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, matrix)+div1idxrev((s+e)/2, e, idx, matrix);
    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, vector<vector<int>> &matrix){
    int m=(s+e)/2, m0=(s0+e0)/2;
    curpossum[s]=0;
    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++;
            }
        }
        return ret;
    }
    ll ret=div3(s, m, s0, e0, matrix)+div3(m, e, s0, e0, matrix);
    for (register int i=s0;i<e0;i++){
        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];
        }
    }
    bool test=0;
    for (register int i=s0;i<m0;i++){
        cur2[i].clear();
        tmp[i].clear();
        register int j1=0, j2=0, sz1=pos[x1][i].size(), sz2=pos[x2][i].size();
        while(j1<sz1 && j2<sz2){
            if (pos[x1][i][j1]==pos[x2][i][j2]){
                cur2[i].push_back(pos[x1][i][j1]);
                test=1;
                if (curpossum[cur2[i].back()+1]-curpossum[i]==(cur2[i].back()-i+1)){
                    ret++;
                }
                j1++, j2++;
            }
            else if (pos[x1][i][j1]<pos[x2][i][j2]) j1++;
            else j2++;
        }
    }
    if (!test) return ret;
    while(x1>s && x2<e-1){
        if (!test) return ret;
        test=0;
        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 (register 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 (register int i=s0;i<m0;i++){
                tmp[i].clear();
                register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x1][i].size();
                while(j1<sz1 && j2<sz2){
                    if (cur2[i][j1]==pos[x1][i][j2]){
                        test=1;
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++, j2++;
                    }
                    else if (cur2[i][j1]<pos[x1][i][j2]) j1++;
                    else j2++;
                }
                swap(tmp[i], cur2[i]);
            }
        }
        else{
            x2++;
            for (register 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 (register int i=s0;i<m0;i++){
                tmp[i].clear();
                register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x2][i].size();
                while(j1<sz1 && j2<sz2){
                    if (cur2[i][j1]==pos[x2][i][j2]){
                        test=1;
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++, j2++;
                    }
                    else if (cur2[i][j1]<pos[x2][i][j2]) j1++;
                    else j2++;
                }
                swap(tmp[i], cur2[i]);
            }
        }
    }
    if (x1==s){
        x2++;
        for (;x2<=e-1;x2++){
            if (!test) return ret;
            test=0;
            for (register 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 (register int i=s0;i<m0;i++){
                tmp[i].clear();
                register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x2][i].size();
                while(j1<sz1 && j2<sz2){
                    if (cur2[i][j1]==pos[x2][i][j2]){
                        test=1;
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++, j2++;
                    }
                    else if (cur2[i][j1]<pos[x2][i][j2]) j1++;
                    else j2++;
                }
                swap(tmp[i], cur2[i]);
            }
        }
    }
    else{
        x1--;
        for (;x1>=s;x1--){
            if (!test) return ret;
            for (register 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 (register int i=s0;i<m0;i++){
                tmp[i].clear();
                register int j1=0, j2=0, sz1=cur2[i].size(), sz2=pos[x1][i].size();
                while(j1<sz1 && j2<sz2){
                    if (cur2[i][j1]==pos[x1][i][j2]){
                        test=1;
                        tmp[i].push_back(cur2[i][j1]);
                        if (curpossum[tmp[i].back()+1]-curpossum[i]==(tmp[i].back()+1-i)) ret++;
                        j1++, j2++;
                    }
                    else if (cur2[i][j1]<pos[x1][i][j2]) j1++;
                    else j2++;
                }
                swap(tmp[i], cur2[i]);
            }
        }
    }
    return ret;
}

ll div2(int s, int e, vector<vector<int>> &matrix){
    if (e-s==1){
        return div1idxrev(1, n-1, s, matrix);
    }
    int m=(s+e)/2;
    ll ret=div2(s, m, matrix)+div2(m, e, matrix);
    for (register int i=0;i<n;i++){
        for (register int j=s;j<m;j++) pos[i][j].clear();
        register 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, matrix);
    return ret;
}

ll solve1(vector<vector<int>> &matrix){
    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, matrix);
    return ret;
}

ll count_rectangles(vector<vector<int>> matrix){
  	n=matrix.size(), M=matrix[0].size();
    if (n<=3) return solve1(matrix);
    else if (M<=2) return 0;
    return div2(1, M-1, matrix);
}

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