Submission #959270

#	Time	Username	Problem	Language	Result	Execution time	Memory
959270		qin	Rectangles (IOI19_rect)	C++17	100 / 100	1457 ms	356372 KiB

rect

#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1; // PAMIETAC, ZE TAM MAM CIAG INDEKSOWANY OD 0
struct segminmax{
		int base;
		struct Node{
				int mn, mx;
				Node(){ mn = inf, mx = 0; }
		};
		vv<Node> t;
		void init(int n, vv<int> &a, vv<int> &b){
				base = 1;
				while(base < n) base <<= 1;
				t.resize(base<<1, Node());
				for(int i = 1; i <= n; ++i) t[i+base-1].mn = b[i-1], t[i+base-1].mx = a[i-1];
				for(int i = base-1; i; --i) t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn), t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx);
		}
		pii query_interval(int l, int r){
				pii res = pii(inf, 0);
				for(l += base-1, r += base; l < r; l >>= 1, r >>= 1){
						if(l & 1) res.fi = min(res.fi, t[l].mn), res.se = max(res.se, t[l].mx), ++l;
						if(r & 1) --r, res.fi = min(res.fi, t[r].mn), res.se = max(res.se, t[r].mx);
				}
				return res;
		}
		pii query(int l, int r){
				if(l <= r) return query_interval(max(1, l), min(base, r));
				return pii(inf, 0);
		}
};
struct seg{
		int base;
		vv<int> t;
		void init(int n){
				base = 1;
				while(base < n) base <<= 1;
				t.resize(base<<1, 0);
		}
		void update(int i, int val){
				for(i += base-1, t[i] = val, i >>= 1; i; i >>= 1) t[i] = t[i<<1]+t[i<<1|1];
		}
		int query_interval(int l, int r){
				int res = 0;
				for(l += base-1, r += base; l < r; l >>= 1, r >>= 1){
						if(l & 1) res += t[l++];
						if(r & 1) res += t[--r];
				}
				return res;
		}
		int query(int l, int r){
				if(l <= r) return query_interval(max(1, l), min(base, r));
				return 0;
		}
};
ll count_rectangles(vv<vv<int>> t){
		int n = ssize(t), m = ssize(t[0]);
		vv<vv<int>> u(n, vv<int>(m, 0)), d(n, vv<int>(m, n-1)), l(n, vv<int>(m, inf)), r(n, vv<int>(m, -1));
		vv<int> st;
		for(int i = 0; i < n; ++i){ 
				for(int j = 0; j < m; ++j){ // przedzialy gdzie ja to prawy koniec
						while(ssize(st) && t[i][st.back()] < t[i][j]) st.pop_back();
						if(ssize(st)) r[i][j] = st.back();
						st.emplace_back(j);
				} st = vv<int>();
				for(int j = m-1; ~j; --j){  // przedzialy gdzie ja to lewy koniec
						while(ssize(st) && t[i][st.back()] < t[i][j]) st.pop_back();
						if(ssize(st)) l[i][j] = st.back();
						st.emplace_back(j);
				} st = vv<int>();
		}
		for(int j = 0; j < m; ++j){ 
				for(int i = 0; i < n; ++i){ // przedzialy gdzie ja to dolny koniec (ustawiamy najblizszego do gory)
						while(ssize(st) && t[st.back()][j] < t[i][j]) st.pop_back();
						if(ssize(st)) u[i][j] = st.back();
						st.emplace_back(i);
				} st = vv<int>();
				for(int i = n-1; ~i; --i){ // przedzialy gdzie ja to gorny koniec (ustawiamy najblizszego na dole)
						while(ssize(st) && t[st.back()][j] < t[i][j]) st.pop_back();
						if(ssize(st)) d[i][j] = st.back();
						st.emplace_back(i);
				} st = vv<int>();
		}
		//~ for(int i = 0; i < n; ++i){
				//~ for(int j = 0; j < m; ++j) printf("%d ", d[i][j]);
				//~ pn;
		//~ }
		ll result = 0;
		vv<segminmax> segm(n);
		vv<vv<int>> rem(n+1);
		seg seg; seg.init(n);
		vv<pii> queries(n+2);
		for(int i = 0; i < n; ++i) segm[i].init(m, u[i], d[i]);
		vv<pii> mp;
		for(int i = 1; i < n-1; ++i){
				mp = vv<pii>();
				for(int j = 0; j < m; ++j) if(l[i][j] != inf) mp.emplace_back(j, l[i][j]);
				for(int j = 0; j < m; ++j) if(r[i][j] != -1 && l[i][r[i][j]] != j) mp.emplace_back(r[i][j], j);
				for(pii pd : mp){
						int L = pd.fi+1, R = pd.se-1;
						if(R < L) continue;
						++L, ++R; // do przedzialowca
						int sz = 1;
						for(int j = i+1; j < n-1; ++j){
								if(l[j][pd.fi] == pd.se || r[j][pd.se] == pd.fi){
										++sz;
										if(l[j][pd.fi] == pd.se) l[j][pd.fi] = inf;
										if(r[j][pd.se] == pd.fi) r[j][pd.se] = -1;
								}
								else break;
						}
						//~ queries.resize(sz+2);
						for(int j = i-1; j <= i+sz; ++j) queries[j-(i-1)] = segm[j].query(L, R);
						for(int j = i; j < i+sz; ++j){
								//~ printf("%d %d %d: %lld\n", j, l-1, r-1, result);
								for(int &x : rem[j-i]) seg.update(x, 0);
								rem[j-i].clear();
								int endpoint = queries[j-1-i+1].fi;
								if(j < endpoint){
										seg.update(j-i+1, 1);
										rem[min(sz, endpoint-i)].emplace_back(j-i+1);
								}
								endpoint = queries[j+1-i+1].se;//segm[j+1].query_max(l, r);
								result += seg.query(max(-1, endpoint-i)+2, j-i+1);
								//~ printf("%d %d %d: %d %lld\n", j, l-1, r-1, endpoint, result);
						}
						for(int &x : rem[sz]) seg.update(x, 0);
						rem[sz].clear();//, queries.clear();
				}
		}
		return result;
}
#ifdef LOCAL
int main(){
		int T = 1;
		for(++T; --T; ){
				int n, m; scanf("%d%d", &n, &m);
				vv<vv<int>> t(n, vv<int>(m, 0));
				for(int i = 0; i < n; ++i)
						for(int j = 0; j < m; ++j) scanf("%d", &t[i][j]);
				ll result = count_rectangles(t);
				printf("%lld\n", result);
		}
		return 0;
}
#endif

• 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