Submission #950629

#	Time	Username	Problem	Language	Result	Execution time	Memory
950629		qin	Rectangles (IOI19_rect)	C++17	72 / 100	5087 ms	1048576 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 i, int s, int e, int x, int y){
				if(x <= s && e <= y) return pii(t[i].mn, t[i].mx);
				int mid = (s+e)>>1; pii result = pii(inf, 0), tmp;
				if(x <= mid) tmp = query_interval(i<<1, s, mid, x, y), result.fi = min(result.fi, tmp.fi), result.se = max(result.se, tmp.se);
				if(mid < y) tmp = query_interval(i<<1|1, mid+1, e, x, y), result.fi = min(result.fi, tmp.fi), result.se = max(result.se, tmp.se);
				return result;
		}
		pii query(int l, int r){
				if(l <= r) return query_interval(1, 1, base, 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 i, int s, int e, int x, int y){
				if(x <= s && e <= y) return t[i];
				int mid = (s+e)>>1, result = 0;
				if(x <= mid) result += query_interval(i<<1, s, mid, x, y);
				if(mid < y) result += query_interval(i<<1|1, mid+1, e, x, y);
				return result;
		}
		int query(int l, int r){
				if(l <= r) return query_interval(1, 1, base, 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));
		vv<map<pii, int>> mp(n);
		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)) mp[i][pii(st.back(), j)] = 1;
						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)) mp[i][pii(j, st.back())] = 1;
						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;
		for(int i = 0; i < n; ++i) segm[i].init(m, u[i], d[i]);
		for(int i = 1; i < n-1; ++i){
				for(pair<pii, int> pd : mp[i]) if(pd.se){
						int l = pd.fi.fi+1, r = pd.fi.se-1;
						if(r < l) continue;
						++l, ++r; // do przedzialowca
						int sz = 1;
						for(int j = i+1; j < n-1; ++j) if(mp[j][pd.fi]) ++sz, mp[j][pd.fi] = 0;
													   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: 0 / 28