Submission #144277

#	Time	Username	Problem	Language	Result	Execution time	Memory
144277		shdut	Rectangles (IOI19_rect)	C++14	0 / 100	10 ms	10488 KiB

rect

#include "rect.h"
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;

#define inf 1000000007
#define SZ(x) x.size()
#define N 2505
#define pb push_back
#define x first
#define y second
#define ls p<<1
#define rs p<<1|1
#define vi std::vector<int>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define DBG(x) cerr << (#x) << "=" << x << "\n";

int U[N][N], L[N][N], q[N], T[N], H[N], Q[N][N];
long long count_rectangles(std::vector<std::vector<int> > a) {
    //for(auto &o : a){
    //    for(auto &x : o)cerr << x << " ";
    //    cerr << "\n";
    //}
    int n = SZ(a), m = SZ(a[0]);
    rep(i, 0, n){
        int t = 0;
        rep(j, 0, m){
            while(t && a[i][q[t-1]] < a[i][j])t--;
            L[i][j] = t == 0 ? 0 : q[t-1];
            //cerr << L[i][j] << " ";
            q[t++] = j;
        }
        //cerr << "\n";
    }
    rep(j, 0, m){
        int t = 0;
        rep(i, 0, n){
            while(t && a[q[t-1]][j] < a[i][j])t--;
            U[i][j] = t == 0 ? 0 : q[t-1];
            //cerr << U[i][j] << " ";
            q[t++] = i;
        }
        //cerr << "\n";
    }
    rep(i, 0, m)H[i] = T[i] = 0;
    long long ans = 0;
    rep(i, 0, n){
        int t = 0;
        rep(j, 0, m-1){
            while(t && U[i][q[t-1]] <= U[i][j])t--;
            q[t++] = j;
            int k = j+1;
            //DBG(U[i][j])
            //while(H[k] < T[k] && Q[k][H[k]] <= U[i][j]){
            //    H[k]++;
            //}
            if(i >=2 && j){
                int x = t-1, y = 0, w = L[i-1][k];
                while(y < T[k] && Q[k][y] <= U[i][j])y++;
                //cerr << i << " " << j << ":\n";
                //cerr << q[x] << " " << Q[k][y] << " " << U[i][q[x]] << ", " << L[Q[k][y]][k] << "\n"; 
                while(x >= 0 && q[x] > w){
                    while(y < T[j] && Q[k][y] <= U[i][q[x]])y++;
                    while(y < T[j] && L[Q[k][y]][k] >= q[x])y++;
                    if(y == T[k])break;
                    int z = y == 0 ? 1 : Q[k][y-1] + 1;
                    //cerr << z << " " << i << ", " << q[x] << " " << j << "\n";
                    ans += (j - q[x] + 1) * max(i - z, 0);
                    x--;
                }
            }
        }
        rep(j, 0, m){
            while(H[j] < T[j] && L[Q[j][T[j]-1]][j] <= L[i][j])T[j]--;
            Q[j][T[j]++] = i;
        }
    }
    return ans;
}

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