Submission #1221215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221215		Malix	Rectangles (IOI19_rect)	C++20	100 / 100	4049 ms	857424 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int b[2500][2500][4];

long long count_rectangles(std::vector<std::vector<int>> a) {
	int n=a.size(),m=a[0].size();
    vector<vii> c(m,vii(m)),d(n,vii(n));
    REP(i,0,n)REP(j,0,m)REP(k,0,4)b[i][j][k]=-1;
    REP(i,0,n){
        stack<pi> s;
        REP(j,0,m){
            while(!s.empty()&&s.top().F<=a[i][j])s.pop();
            if(!s.empty())b[i][j][1]=s.top().S;
            s.push({a[i][j],j});
        }
        s=stack<pi>();
        for(int j=m-1;j>=0;j--){
            while(!s.empty()&&s.top().F<=a[i][j])s.pop();
            if(!s.empty())b[i][j][3]=s.top().S;
            s.push({a[i][j],j});
        }
        REP(j,0,m)if(b[i][j][1]!=-1&&b[i][j][3]!=-1){
            b[i][j][1]++;
            b[i][j][3]--;
        }
        REP(j,0,m)if(b[i][j][1]!=-1&&b[i][j][3]!=-1)c[b[i][j][1]][b[i][j][3]].PB(i);
    }
    REP(i,0,m)REP(j,0,m){
        sort(all(c[i][j]));
        c[i][j].erase(unique(all(c[i][j])),c[i][j].end());
    }
    REP(j,0,m){
        stack<pi> s;
        REP(i,0,n){
            while(!s.empty()&&s.top().F<=a[i][j])s.pop();
            if(!s.empty())b[i][j][0]=s.top().S;
            s.push({a[i][j],i});
        }
        s=stack<pi>();
        for(int i=n-1;i>=0;i--){
            while(!s.empty()&&s.top().F<=a[i][j])s.pop();
            if(!s.empty())b[i][j][2]=s.top().S;
            s.push({a[i][j],i});
        }
        REP(i,0,n)if(b[i][j][0]!=-1&&b[i][j][2]!=-1){
            b[i][j][0]++;
            b[i][j][2]--;
        }
        REP(i,0,n)if(b[i][j][0]!=-1&&b[i][j][2]!=-1)d[b[i][j][0]][b[i][j][2]].PB(j);
    }
    REP(i,0,n)REP(j,0,n){
        sort(all(d[i][j]));
        d[i][j].erase(unique(all(d[i][j])),d[i][j].end());
    }
    vii arr;
    REP(i,0,n)REP(j,0,m){
        bool flag=1;
        REP(k,0,4)if(b[i][j][k]==-1)flag=0;
        if(flag)arr.PB({b[i][j][0],b[i][j][1],b[i][j][2],b[i][j][3]});
    }
    sort(all(arr));
    arr.erase(unique(all(arr)),arr.end());
    ll ans=0;
    for(auto u:arr){
        int x1=u[0],y1=u[1],x2=u[2],y2=u[3];
        auto it1=lower_bound(all(c[y1][y2]),x1);
        auto it2=lower_bound(all(d[x1][x2]),y1);
        if(it1==c[y1][y2].end()||it2==d[x1][x2].end())continue;
        if((*it1!=x1)||(*it2!=y1))continue;
        int ps1=it1-c[y1][y2].begin(),ps2=it2-d[x1][x2].begin();
        if(ps1+x2-x1>=(int)c[y1][y2].size()||c[y1][y2][ps1+x2-x1]!=x2)continue;
        if(ps2+y2-y1>=(int)d[x1][x2].size()||d[x1][x2][ps2+y2-y1]!=y2)continue;
        ans++;
    }
    return ans;
}

• 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