Submission #207935

#	Time	Username	Problem	Language	Result	Execution time	Memory
207935		ToMmyDong	Rectangles (IOI19_rect)	C++14	49 / 100	302 ms	144760 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 = 702;

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;
vector<pii> h[MAXN][MAXN], g[MAXN][MAXN];

int solve (int i, int j) {
    vector<pair<int,int> > qry;
    for (auto p : h[i][j]) {
        qry.emplace_back(p.Y, p.X);
    }
    sort(qry.begin(), qry.end());

    int res = 0;
    int idx = 0;

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

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

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

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

    debug(i, j);
    debug(h[i][j]);
    debug(g[j][i]);

    return res;
}

vector<short> pa[MAXN][MAXN];
void build (vector<pii> res[MAXN][MAXN]) {
    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) {
                    pa[stk.back()][j].eb(i);
                    debug(stk.back(), j, i);
                }
                stk.pop_back();
            }
            if (stk.size()) {
                debug(i, stk);
                if (stk.back() < j - 1) {
                    debug(stk.back(), j, i);
                    pa[stk.back()][j].eb(i);
                }
            }

            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;
            for (int k=SZ(pa[l][r])-1; k>=0; k--) {
                if (k!=SZ(pa[l][r])-1 && pa[l][r][k]+1!=pa[l][r][k+1]) {
                    len = 0;
                }
                len++;
                res[pa[l][r][k]-1][l].eb(r-l-1, len);
            }
        }
    }

    for (int i=0; i<MAXN;i++) {
        for (int j=0;j<MAXN; j++) {
            pa[i][j].clear();
            pa[i][j].shrink_to_fit();
        }
    }
}


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);

	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: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28