Submission #596461

#	Time	Username	Problem	Language	Result	Execution time	Memory
596461		keta_tsimakuridze	Rectangles (IOI19_rect)	C++14	100 / 100	2364 ms	576064 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define s second
#define f first
const int N = 2500 + 5;
struct xx {
    int l, U;
};
struct yy {
    int u, L;
};
int t[N], n, m;
vector<vector<xx> > x[N];
vector<vector<yy> > y[N];
void upd(int id, int v) {
    ++id;
    for(id; id <= m + 1; id += id & (-id)) t[id] += v;
}
int get(int id) {
    int ans = 0;
    ++id;
    for(id; id >= 1; id -= id & (-id)) ans += t[id];
    return ans;
}
bool cmp1(xx a, xx b) {
    return (a.l < b.l);
}
bool cmp(yy a, yy b) {
    return (a.u < b.u);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	 n = a.size(), m = a[0].size();

	for(int i = 0; i < n; i++) {
        stack<int> st; x[i].resize(m); y[i].resize(m);
        for(int j = 0; j < m; j++) {
            int f = 0;
            while(st.size() && a[i][st.top()] <= a[i][j]) {
                f |= (a[i][st.top()] == a[i][j]);
                if(j && st.top() + 1 <= j - 1)
                x[i][j - 1].push_back({st.top() + 1, 0});
                st.pop();
            }
            if(!f && st.size() && st.top() + 1 <= j - 1) x[i][j - 1].push_back({st.top() + 1, 0});
            st.push(j);
        }
	}
	for(int j = 0; j < m; j++) {
        stack<int> st;
        for(int i = 0; i < n; i++) {
            int f = 0;
            while(st.size() && a[st.top()][j] <= a[i][j]) {
                f |= (a[st.top()][j] == a[i][j]);
                if(i && st.top() + 1 <= i - 1)
                y[i - 1][j].push_back({st.top() + 1, 0});
                st.pop();
            }
            if(!f && st.size() && st.top() + 1 <= i - 1) y[i- 1][j].push_back({st.top() + 1, 0});
            st.push(i);
        }
    }
    //long long ans = 0;
    long long ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            int l = 0;
            vector<pii> v;
            reverse(x[i][j].begin(), x[i][j].end());
            reverse(y[i][j].begin(), y[i][j].end());
            for(int k = 0; k < x[i][j].size(); k++) {

                while(i && l < x[i - 1][j].size() && x[i - 1][j][l].l < x[i][j][k].l) ++l;
                if(!i || l == x[i - 1][j].size() || x[i - 1][j][l].l != x[i][j][k].l) x[i][j][k].U = i;
                else x[i][j][k].U = x[i - 1][j][l].U;
                v.push_back({x[i][j][k].U, x[i][j][k].l});
            }

            l = 0;
            for(int k = 0; k < y[i][j].size(); k++) {
                while(j && l < y[i][j - 1].size() && y[i][j - 1][l].u < y[i][j][k].u) ++l;
                if(!j || l == y[i][j - 1].size() || y[i][j - 1][l].u != y[i][j][k].u) y[i][j][k].L = j;
                else y[i][j][k].L = y[i][j - 1][l].L;
            }
            vector <yy> Y = y[i][j];
            vector<int> rem;
            sort(v.begin(), v.end());
            for(int k = (int)v.size() - 1; k >= 0; k--) {
                //  (l, r) -- U ebi da (u, d) ebi -- L
                // ramdenia u >= U da L <= l
                int U = v[k].f, l = v[k].s;
                while(Y.size() && Y.back().u >= v[k].f) {
                    upd(Y.back().L, 1);
                    rem.push_back(Y.back().L);
                    Y.pop_back();
                }
                ans += get(l);
            }
            while(rem.size()) upd(rem.back(), -1), rem.pop_back();
        }
    }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'void upd(int, int)':
rect.cpp:19:9: warning: statement has no effect [-Wunused-value]
   19 |     for(id; id <= m + 1; id += id & (-id)) t[id] += v;
      |         ^~
rect.cpp: In function 'int get(int)':
rect.cpp:24:9: warning: statement has no effect [-Wunused-value]
   24 |     for(id; id >= 1; id -= id & (-id)) ans += t[id];
      |         ^~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:72:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<xx>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for(int k = 0; k < x[i][j].size(); k++) {
      |                            ~~^~~~~~~~~~~~~~~~
rect.cpp:74:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<xx>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 while(i && l < x[i - 1][j].size() && x[i - 1][j][l].l < x[i][j][k].l) ++l;
      |                            ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:75:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<xx>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 if(!i || l == x[i - 1][j].size() || x[i - 1][j][l].l != x[i][j][k].l) x[i][j][k].U = i;
      |                          ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:81:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<yy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for(int k = 0; k < y[i][j].size(); k++) {
      |                            ~~^~~~~~~~~~~~~~~~
rect.cpp:82:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<yy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                 while(j && l < y[i][j - 1].size() && y[i][j - 1][l].u < y[i][j][k].u) ++l;
      |                            ~~^~~~~~~~~~~~~~~~~~~~
rect.cpp:83:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<yy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |                 if(!j || l == y[i][j - 1].size() || y[i][j - 1][l].u != y[i][j][k].u) y[i][j][k].L = j;
      |                          ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:92:21: warning: unused variable 'U' [-Wunused-variable]
   92 |                 int U = v[k].f, l = v[k].s;
      |                     ^

• 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