Submission #889565

#	Time	Username	Problem	Language	Result	Execution time	Memory
889565		vjudge1	Rectangles (IOI19_rect)	C++17	37 / 100	5092 ms	82844 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
 
 
using namespace std;
 
using vi = vector<int>;
using i4 = array<int, 4>;
using vi4 = vector<i4>;
 
void extract(int n, int m, vector<vi> &V, vi4 &V1) {
    vector<stack<int> > lin(m);
    for(int j = 0; j < m; ++j)
        lin[j].push(0);
    set<int> Cur;
    for(int i = 1; i < n; ++i) {
        vector<pair<int, int> > Ult, UrmU; /// perechi (linie, j din trecut)
        for(int j = 0; j < m; ++j) {
            Cur.clear();
            int uv = V[i][j];
            while(!lin[j].empty() && V[i][j] > V[lin[j].top()][j]) {
                if(V[lin[j].top()][j] != uv) {
                    Cur.insert(lin[j].top());
                    uv = V[lin[j].top()][j];
                }
                lin[j].pop();
            }
            if(!lin[j].empty()) {
                if(V[lin[j].top()][j] != uv) { // desc
                    Cur.insert(lin[j].top());
                    uv = V[lin[j].top()][j];
                }
            }
            lin[j].push(i);
            UrmU.clear();
            for(auto [l, jv] : Ult) {
                if(Cur.count(l)) {
                    UrmU.push_back({l, jv});
                    Cur.erase(l);
                } else {
                    if(abs(l - i) > 1 && j - 1 - jv >= 0)
                        V1.push_back(i4{l, i, jv, j - 1});
                }
            }
            swap(Ult, UrmU);
            for(auto vc : Cur)
                Ult.push_back({vc, j});
        }
        for(auto [l, jv] : Ult) {
            if(abs(l - i) > 1 && m - 1 - jv >= 0)
                V1.push_back(i4{l, i, jv, m - 1});
        }
    }
}
 
struct CEVA {
    int MAX_V = 14000002;
    int CMAGIC = 7000001;
 
    vector<tuple<int, int, int> > VQ;
    vector<int> V;
 
    void fake_update(int v1, int v2, int v3) {
        v1 += CMAGIC;
        v2 += CMAGIC;
        v3 += CMAGIC;
        while(v1 < MAX_V) {
            int a = v2;
            while(a < MAX_V) {
                int b = v3;
                while(b < MAX_V) {
                    VQ.push_back({v1, a, b});
                    b += b & -b;
                }
                a += a & -a;
            }
            v1 += v1 & -v1;
        }
    }
 
    void init() {
        sort(VQ.begin(), VQ.end());
        VQ.resize(unique(VQ.begin(), VQ.end()) - VQ.begin());
        V.assign(VQ.size(), 0);
    }
 
    int id(tuple<int, int, int> q) {
        int p = lower_bound(VQ.begin(), VQ.end(), 
                q) - VQ.begin();
        if(VQ[p] != q) p = -1;
        return p;
    }
 
    void update(int v1, int v2, int v3) {
        v1 += CMAGIC;
        v2 += CMAGIC;
        v3 += CMAGIC;
        while(v1 < MAX_V) {
            int a = v2;
            while(a < MAX_V) {
                int b = v3;
                while(b < MAX_V) {
                    V[id({v1, a, b})] += 1;
                    b += b & -b;
                }
                a += a & -a;
            }
            v1 += v1 & -v1;
        }
    }
 
    int query(int v1, int v2, int v3) {
        v1 += CMAGIC;
        v2 += CMAGIC;
        v3 += CMAGIC;
        int re = 0;
        while(v1) {
            int a = v2;
            while(a) {
                int b = v3;
                while(b) {
                    int p = id({v1, a, b});
                    if(p != -1) re += V[p];
                    b -= b & -b;
                }
                a -= a & -a;
            }
            v1 -= v1 & -v1;
        }
        return re;
    }
};
 
long long count_rectangles(std::vector<std::vector<int> > V) {
    int n = V.size(), m = V[0].size();
    vector<vi> VT(m, vi(n, 0));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j) 
            VT[j][i] = V[i][j];
 
    vi4 V1, V2;
 
    extract(n, m, V, V1);
    extract(m, n, VT, V2);
    for(auto &it : V2) {
        swap(it[0], it[2]);
        swap(it[1], it[3]);
    }
 
    for(auto &it : V1) {
        ++it[0];
        --it[1];
    }
 
    for(auto &it : V2) {
        ++it[2];
        --it[3];
    }
 
 
    for(auto &it : V1) {
        it[0] *= -1;
        it[3] *= -1;
    }
    for(auto &it : V2) {
        it[0] *= -1;
        it[3] *= -1;
    }

    using i3 = array<int, 3>;
 
    sort(V1.begin(), V1.end(), [&](auto a, auto b) {
            return a[0] < b[0];
    });
    sort(V2.begin(), V2.end(), [&](auto a, auto b) {
            return a[0] < b[0];
    });
    int p = 0;
    vector<i3> W;
    long long re = 0;
    for(auto it : V2) {
        while(p < V1.size() && V1[p][0] <= it[0]) {
            W.push_back(i3{V1[p][1], V1[p][2], V1[p][3]});
            ++p;
        }
        for(auto it2 : W) {
            int ok = 1;
            for(int i = 0; i < 3; ++i)
                ok &= it[i + 1] >= it2[i];
            re += ok;
        }
    }
	return re;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:186:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |         while(p < V1.size() && V1[p][0] <= it[0]) {
      |               ~~^~~~~~~~~~~

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