Submission #207940

#	Time	Username	Problem	Language	Result	Execution time	Memory
207940		ToMmyDong	Rectangles (IOI19_rect)	C++14	100 / 100	2936 ms	345080 KiB

rect

#include "rect.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<short,short> pii;
#define ALL(i) i.begin(),i.end()
#define X first
#define Y second

#define eb emplace_back
#define SZ(i) int(i.size())
#ifdef tmd
#define debug(...) fprintf(stderr,"%d (%s) = ",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do (T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do (T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream &printRng (IT bg, IT ed, ostream &os) {
    os<<"{";
    for (IT it=bg; it!=ed; it++) {
        if (it!=bg) {
            os<<",";
        }
        os<<(*it);
    }
    return os<<"}";
}
template<typename T> ostream &operator << (ostream &os, vector<T> &vec) {
    return printRng(vec.begin(), vec.end(), os);
}
template<typename T> ostream &operator << (ostream &os, pair<T,T> &vec) {
    return os<<"{"<<vec.first<<","<<vec.second<<"}";
}
template<typename T> void pary (T bg, T ed) {
    printRng(bg,ed,cerr);
    cerr<<endl;
}
#else
#define debug(...)
#define pary(...)
#endif // tmd

const int MAXN = 2502;

int n, m;

int bit[MAXN];

void add (int x, int y) {
    for (x++;x<MAXN;x+=-x&x) {
        bit[x] += y;
    }
}

int sqry (int x) {
    int ret = 0;
    for (x++;x>0; x-=-x&x) {
        ret += bit[x];
    }
    return ret;
}

vector<vector<int> > G;

struct Edge {
    pii dt;
    int nxt;
} edge[MAXN*MAXN*2];
int h[MAXN][MAXN], g[MAXN][MAXN], cnt;

void addEdge (int x, int y, pii dt, int v[MAXN][MAXN]) {
    edge[cnt++] = {dt, v[x][y]};
    v[x][y] = cnt - 1;
}

struct Node {
    short x;
    int nxt;
} node[MAXN*MAXN*2];
int pa[MAXN][MAXN], ncnt;

void addNode (int x, int y, short dt, int v[MAXN][MAXN]) {
    node[ncnt++] = {dt, v[x][y]};
    v[x][y] = ncnt - 1;
}

int solve (int i, int j) {
    vector<pair<int,int> > qry, gg;
    for (int id=h[i][j]; id!=-1; id=edge[id].nxt) {
        qry.emplace_back(edge[id].dt);
        swap(qry.back().first, qry.back().second);
    }
    for (int id=g[j][i]; id!=-1; id=edge[id].nxt) {
        gg.emplace_back(edge[id].dt);
    }
    reverse(ALL(gg));

    sort(qry.begin(), qry.end());

    int res = 0;
    int idx = 0;

    vector<int> opr;
    int sum = 0;
    for (auto p : qry) {

        while (idx < int(gg.size()) && gg[idx].X <= p.X) {
            add(gg[idx].Y, 1);
            sum ++;
            opr.eb(gg[idx].Y);
            idx++;
        }

        res += sum - sqry(p.Y-1);
    }

    for (auto p : opr) {
        add(p, -1);
    }

    if (res) {
        debug(i, j, res);
        debug(qry);
        debug(gg);
    }

    return res;
}

void build (int res[MAXN][MAXN]) {
	memset(pa, -1, sizeof(pa));
    ncnt = 0;
    vector<int> stk;
    for (int i=0; i<n; i++) {
        stk.clear();
        for (int j=0; j<m; j++) {
            while (stk.size() && G[i][stk.back()] < G[i][j]) {
                if (stk.back() < j - 1) {
                    addNode(stk.back(),j,i,pa);
                    debug(stk.back(), j, i);
                }
                stk.pop_back();
            }
            if (stk.size()) {
                if (stk.back() < j - 1) {
                    debug(stk.back(), j, i);
                    addNode(stk.back(),j,i,pa);
                }
            }

            while (stk.size() && G[i][stk.back()] == G[i][j]) {
                stk.pop_back();
            }
            stk.eb(j);
        }
    }
//    debug("hf");

    for (int l=0; l<m; l++) {
        for (int r=l+2; r<m; r++) {
            int len = 0;

            int ls = -1;
            for (int k=pa[l][r]; k!=-1; k=node[k].nxt) {
                int x = node[k].x;
                if (ls!=-1 && x+1!=ls) {
                    len = 0;
                }
                len++;
                addEdge(x-1,l,{r-l-1, len},res);
                ls = x;
            }
        }
    }
}


vector<vector<int> > flip (vector<vector<int> > vec) {
    vector<vector<int> > res;
    for (int j=0; j<SZ(vec[0]); j++) {
        vector<int> cur;
        for (int i=0; i<SZ(vec); i++) {
            cur.emplace_back(vec[i][j]);
        }
        res.emplace_back(cur);
    }
    swap(n, m);
    return res;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
    G = a;
	n = a.size();
	m = a[0].size();
	debug(n, m);

	memset(h, -1, sizeof(h));
	memset(g, -1, sizeof(g));

	build(h);
	G = flip(G);
	debug("FL");
	build(g);
	G = flip(G);

    ll res = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            res += solve(i, j);
        }
    }
    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