제출 #1069481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1069481		12345678	Rectangles (IOI19_rect)	C++17	100 / 100	3992 ms	832072 KiB

rect

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

using namespace std;

const int nx=2505;

int jr[nx][nx], jdn[nx][nx];
vector<pair<int, int>> dpr[nx][nx], dpdn[nx][nx];
stack<int> s;

struct fenwick
{
    int d[nx];
    void add(int i, int vl)
    {
        while (i<nx) d[i]+=vl, i+=(i&-i);
    }
    int query(int i)
    {
        int tmp=0;
        while (i>0) tmp+=d[i], i-=(i&-i);
        return tmp;
    }
} f;

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n=a.size(), m=a[0].size();
	long long res=0, res2=0;
    for (int i=0; i<n; i++) for (int j=0; j<m; j++) jdn[i][j]=jr[i][j]=-1, dpr[i][j].clear(), dpdn[i][j].clear();
    for (int i=n-1; i>=0; i--)
    {
        while (!s.empty()) s.pop();
        for (int j=m-1; j>=0; j--)
        {
            while (!s.empty()&&a[i][j]>=a[i][s.top()]) s.pop();
            if (!s.empty()) jr[i][j]=s.top();
            s.push(j);
            int curj=j+1;
            while (curj<m&&a[i][j]>a[i][curj])
            {
                curj=jr[i][curj];
                if (curj==-1) break;
                auto itr=lower_bound(dpr[i+1][j].begin(), dpr[i+1][j].end(), make_pair(curj, 0));
                if (itr!=dpr[i+1][j].end()&&itr->first==curj) dpr[i][j].push_back({curj, itr->second});
                else dpr[i][j].push_back({curj, i+1});
            }
        }
    }
    for (int j=m-1; j>=0; j--)
    {
        while (!s.empty()) s.pop();
        for (int i=n-1; i>=0; i--)
        {
            while (!s.empty()&&a[i][j]>=a[s.top()][j]) s.pop();
            if (!s.empty()) jdn[i][j]=s.top();
            s.push(i);
            int curi=i+1;
            while (curi<n&&a[i][j]>a[curi][j])
            {
                curi=jdn[curi][j];
                if (curi==-1) break;
                //if (i==0&&j==1) cout<<"jump "<<curi<<'\n';
                auto itr=lower_bound(dpdn[i][j+1].begin(), dpdn[i][j+1].end(), make_pair(curi, 0));
                //if (i==0&&j==1) cout<<"itr "<<itr->first<<' '<<itr->second<<'\n'; 
                if (itr!=dpdn[i][j+1].end()&&itr->first==curi) dpdn[i][j].push_back({curi, itr->second});
                else dpdn[i][j].push_back({curi, j+1});
            }
        }
    }
    for (int i=0; i<n-1; i++)
    {
        for (int j=0; j<m-1; j++)
        {
            for (auto &x:dpr[i+1][j]) swap(x.first, x.second);
            for (auto x:dpr[i+1][j]) for (auto y:dpdn[i][j+1]) if (x.first>=y.first&&x.second<=y.second) res++;
            /*
            sort(dpr[i+1][j].begin(), dpr[i+1][j].end(), [](pair<int, int> a, pair<int, int> b){return a.second>b.second;});
            sort(dpdn[i][j+1].begin(), dpdn[i][j+1].end());
            reverse(dpdn[i][j+1].begin(), dpdn[i][j+1].end());
            int idx=0;
            for (auto x:dpdn[i][j+1])
            {
                while (idx<dpr[i+1][j].size()&&dpr[i+1][j][idx].second>=x.first) f.add(dpr[i+1][j][idx].first, 1), idx++;
                res+=f.query(x.second);
            }
            while (--idx>=0) f.add(dpr[i+1][j][idx].first, -1);
            */
           /*
            if (i==0&&j==1)
            {
                cout<<"dpr\n";
                for (auto x:dpr[i+1][j]) cout<<x.first<<' '<<x.second<<'\n';
                cout<<"dpdn\n";
                for (auto x:dpdn[i][j+1]) cout<<x.first<<' '<<x.second<<'\n';
            }
            cout<<"res "<<i<<' '<<j<<' '<<res<<'\n';
            */
        }
    }
	return res;
}

/*
4 5
5 2 1 4 3
24 21 4 2 4
3 5 2 12 10
45 3 3 5 5
*/

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:29:19: warning: unused variable 'res2' [-Wunused-variable]
   29 |  long long res=0, res2=0;
      |                   ^~~~

• 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