Submission #1049085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049085		NotLinux	Rectangles (IOI19_rect)	C++17	100 / 100	2323 ms	807424 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
struct Fenwick{
	vector < int > tree;
	int tree_len;
	Fenwick(int len){
		tree_len = len;
		tree.assign(len + 5 , 0);
	}
	int pref_sum(int p){
		int ret = 0;
		while(p > 0){
			ret += tree[p];
			p -= p & (-p);
		}
		return ret;
	}
	int query(int l , int r){
		return pref_sum(r) - pref_sum(l-1);
	}
	void update(int p , int x){
		while(p <= tree_len){
			tree[p] += x;
			p += p & (-p);
		}
	}
};
long long count_rectangles(vector<vector<int> > a) {
	int n = sz(a) , m = sz(a[0]);
	int nxt_right[n][m] , nxt_down[n][m];
	memset(nxt_right , -1 , sizeof(nxt_right));
	memset(nxt_down , -1 , sizeof(nxt_down));
	for(int i = 0;i<n;i++){
		stack < int > st;
		for(int j = m-1;j>=0;j--){
			while(sz(st) and a[i][st.top()] <= a[i][j])st.pop();
			if(sz(st))nxt_right[i][j] = st.top();
			st.push(j);
		}
	}
	for(int j = 0;j<m;j++){
		stack < int > st;
		for(int i = n-1;i>=0;i--){
			while(sz(st) and a[st.top()][j] <= a[i][j])st.pop();
			if(sz(st))nxt_down[i][j] = st.top();
			st.push(i);
		}
	}
	vector < pair < int , int > > ranges_right[n][m] , ranges_down[n][m];
	for(int i = n-1;i>=0;i--){
		for(int j = m-1;j>=0;j--){
			// going to right
			int cury = j+1;
			while(cury < m and a[i][j] > a[i][cury]){
				cury = nxt_right[i][cury];
				if(cury == -1)break;
				else if(i != n-1){
					int ptr = lower_bound(all(ranges_right[i+1][j]) , pair<int,int>{cury , 0}) - ranges_right[i+1][j].begin();
					if(ptr < sz(ranges_right[i+1][j]) and cury == ranges_right[i+1][j][ptr].first){
						ranges_right[i][j].push_back({cury , ranges_right[i+1][j][ptr].second});
					}
					else{
						ranges_right[i][j].push_back({cury , i+1});
					}
				}
				else{
					ranges_right[i][j].push_back({cury , i+1});	
				}
			}
			// going to down
			int curx = i+1;
			while(curx < n and a[i][j] > a[curx][j]){
				curx = nxt_down[curx][j];
				if(curx == -1)break;
				else if(j != m-1){
					int ptr = lower_bound(all(ranges_down[i][j+1]) , pair<int,int>{curx , 0}) - ranges_down[i][j+1].begin();
					if(ptr < sz(ranges_down[i][j+1]) and curx == ranges_down[i][j+1][ptr].first){
						ranges_down[i][j].push_back({curx , ranges_down[i][j+1][ptr].second});
					}
					else{
						ranges_down[i][j].push_back({curx , j+1});
					}
				}
				else{
					ranges_down[i][j].push_back({curx , j+1});
				}
			}
		}
	}
	long long ans = 0;
	for(int i = 0;i<n-1;i++){
		for(int j = 0;j<m-1;j++){
			sort(all(ranges_right[i+1][j]) , [&](pair < int , int > &a , pair < int , int > &b){
				if(a.second < b.second)return true;
				else if(a.second > b.second)return false;
				else return a.first < b.first;
			});
			sort(all(ranges_down[i][j+1]));
			Fenwick fen(max(n , m));
			int lp = 0;
			// cout << i << " " << j << endl;
			// cout << "ranges_right : ";for(auto itr : ranges_right[i+1][j])cout << itr.first << "," << itr.second << "   ";cout << endl;
			// cout << "ranges_down : ";for(auto itr : ranges_down[i][j+1])cout << itr.first << "," << itr.second << "   ";cout << endl;
			long long locans = 0;
			for(auto itr : ranges_right[i+1][j]){
				while(lp < sz(ranges_down[i][j+1]) and ranges_down[i][j+1][lp].first <= itr.second){
					fen.update(ranges_down[i][j+1][lp].second , 1);
					lp++;
				}
				locans += fen.query(itr.first , max(n,m));
			}
			// cout << "locans : " << locans << endl;
			ans += locans;
		}
	}
	return ans;
}

• 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