Submission #616026

#	Time	Username	Problem	Language	Result	Execution time	Memory
616026		Bench0310	Rectangles (IOI19_rect)	C++17	100 / 100	3071 ms	587840 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using namespace std;
typedef long long ll;

vector<array<int,2>> get_opt(vector<int> a)
{
    int n=a.size();
    vector<array<int,2>> v;
    stack<int> s;
    for(int i=0;i<n;i++)
    {
        while(!s.empty()&&a[s.top()]<a[i]) s.pop();
        if(!s.empty()&&s.top()+2<=i) v.push_back({s.top(),i});
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(int i=n-1;i>=0;i--)
    {
        while(!s.empty()&&a[s.top()]<a[i]) s.pop();
        if(!s.empty()&&i+2<=s.top()&&a[s.top()]!=a[i]) v.push_back({i,s.top()});
        s.push(i);
    }
    return v;
}

const int N=2500;
int tree[N];

void upd(int p,int d)
{
    for(;p<N;p=(p|(p+1))) tree[p]+=d;
}

int sum(int p)
{
    int s=0;
    for(;p>=0;p=(p&(p+1))-1) s+=tree[p];
    return s;
}

int sum(int l,int r)
{
    return (sum(r)-sum(l-1));
}

ll count_rectangles(vector<vector<int>> a)
{
    int n=a.size();
    int m=a[0].size();
    vector<array<int,3>> events[n][m]; //c,t,r
    vector one(n,vector(n,array<int,2>{-1,0}));
    for(int j=m-1;j>=0;j--)
    {
        vector<int> tmp(n);
        for(int i=0;i<n;i++) tmp[i]=a[i][j];
        auto opt=get_opt(tmp);
        for(auto [l,r]:opt)
        {
            if(one[l][r][0]==j+1) one[l][r][0]=j;
            else one[l][r]={j,j};
            events[l+1][j].push_back({one[l][r][1]+1,1,r-1});
        }
    }
    vector two(m,vector(m,array<int,2>{-1,0}));
    for(int i=n-1;i>=0;i--)
    {
        vector<int> tmp(m);
        for(int j=0;j<m;j++) tmp[j]=a[i][j];
        auto opt=get_opt(tmp);
        for(auto [l,r]:opt)
        {
            if(two[l][r][0]==i+1) two[l][r][0]=i;
            else two[l][r]={i,i};
            events[i][l+1].push_back({r,0,two[l][r][1]});
        }
    }
    ll res=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            auto &e=events[i][j];
            sort(e.begin(),e.end());
            for(auto [c,t,r]:e)
            {
                if(t==0) upd(r,1);
                else res+=sum(r,n-1);
            }
            for(auto [c,t,r]:e) if(t==0) upd(r,-1);
        }
    }
    return res;
}

• 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