Submission #430549

#	Time	Username	Problem	Language	Result	Execution time	Memory
430549		dreezy	Rectangles (IOI19_rect)	C++17	72 / 100	5146 ms	735880 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define mp make_pair

const int maxn = 2.5e3 + 5 ;
vector<pi> rightedges[maxn][maxn];//col row
vector<pi> bottomedges[maxn][maxn];//row col
const int maxval = 7e6+5;

struct SegTree{
	
	
	int st[maxval * 4 + 5];
	
	
	void init(){
		memset(st, 0, sizeof(st));
	}
	void upd(int n, int l , int r, int ind, int val){
		if(l == r) {
			st[n] += val;
			return;
		}
		int mid = (l + r)/2;
		
		if( mid >= ind)
			upd(2*n+1, l,mid, ind, val);
		else
			upd(2*n +2, mid + 1, r, ind, val);
		st[n] =st[2*n+1] + st[2*n+2];
	}
	
	void upd2(int n, int l , int r, int ind, int val){
		if(l == r) {
			st[n] = 0;
			return;
		}
		int mid = (l + r)/2;
		
		if( mid >= ind)
			upd2(2*n+1, l,mid, ind, val);
		else
			upd2(2*n +2, mid + 1, r, ind, val);
		st[n] =st[2*n+1] + st[2*n+2];
	}
	
	void insert(int val){
		upd(0,1, maxval,val, 1 );
	}
	void erase(int val){
		upd2(0,1, maxval,val, 0 );
	}
	
	
	
	int qry(int n, int l, int r, int s , int e){
		
		if(s <= l and e >= r){
		//	cout <<l<<", "<<r<<", "<<s<<", "<<e<<": "<<st[n]<<endl;
			return st[n];
		} 
		int mid = (l + r)/2;
		int ans = 0;
		
		if( mid >= s)
			ans+= qry(2*n+ 1, l, mid, s, e);
		if(mid <e)
			ans+= qry(2*n+2, mid + 1, r, s,e);
		return ans;
	}
	
	int query(int val){
		
		return qry(0,1, maxval, val, maxval);
	}
};

bool cmp(pi a, pi b){
	return a.s == b.s ? a.f < b.f: a.s < b.s;
}

SegTree st;
long long count_rectangles(vector<vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	
	
	
	for(int row = 1; row < n -1; row++){
		stack<int> stck;
		stck.push(0);
		//the stack is always in decreasing order
		//we keep track of what indices work and which ones don't
		for(int col = 1; col <m ; col++){
			while(stck.size()){
				if(stck.top() != col -1){
					rightedges[row][stck.top() +1].pb({col -1, row});
				}
				
				if(a[row][stck.top()] < a[row][col]){
					//if the current cell is taller than the left edge, then no rectangles can be made
					//from left past the current cell
					stck.pop();
				}
				else {
					
					if (a[row][stck.top()] == a[row][col]){
						stck.pop();
					}
					break;
				}
				//else, left is taller than curcell
				//this means that we can build more rectangles
			}
			stck.push(col);
		}
	}
	/*
	for(int row = 1; row < n -1; row++){
		for(int col = 1; col <m ; col++){
			cout << row<<", "<<col<<": ";
			for(pi p : rightedges[row][col])
				cout << p.second<<", "<<p.first<<";";
			cout <<endl;
		}
	}*/
	
	for(int col = 1; col < m -1; col++){
		stack<int> stck;
		stck.push(0);
		//the stack is always in decreasing order
		//we keep track of what indices work and which ones don't
		for(int row = 1; row <n ; row++){
			while(stck.size()){
				if(stck.top() != row -1){
					bottomedges[stck.top() +1][col].pb({row - 1, col});
				}
				
				if(a[stck.top()][col] < a[row][col]){
					//if the current cell is taller than the left edge, then no rectangles can be made
					//from left past the current cell
					stck.pop();
				}
				else {
					
					if (a[stck.top()][col] == a[row][col]){
						stck.pop();
					}
					break;
				}
				//else, left is taller than curcell
				//this means that we can build more rectangles
			}
			stck.push(row);
		}
	}
	/*for(int row = 1; row < n; row++){
		for(int col = 1; col <m -1; col++){
			cout << row<<", "<<col<<": ";
			for(pi p : bottomedges[row][col])
				cout << p.first<<", "<<p.second<<";";
			cout <<endl;
		}
	}*/
	
	for(int row = n -2; row >0; row--){
		for(int col = m-2; col >0; col--){
			//int row_size 
			
			for(int i =0; i<rightedges[row][col].size(); i++){
				
				auto it = lower_bound(rightedges[row+1][col].begin(), rightedges[row+1][col].end(),mp(rightedges[row][col][i].f, -1));
				if(it != rightedges[row + 1][col].end() and it->f == rightedges[row][col][i].f)
					rightedges[row][col][i].s = it ->s;
			}
			
			for(int i =0; i<bottomedges[row][col].size(); i++){
				
				auto it = lower_bound(bottomedges[row][col+1].begin(), bottomedges[row][col+1].end(),mp(bottomedges[row][col][i].f, -1));
				if(it != bottomedges[row][col+1].end() and it->f == bottomedges[row][col][i].f)
					bottomedges[row][col][i].s = it ->s;
			}
		}
	}
	
	ll ans = 0;

	for(int row = 1; row< n -1; row++){
		for(int col = 1; col < m-1; col++){
			sort(rightedges[row][col].begin(), rightedges[row][col].end(), cmp);//sort by second
			sort(bottomedges[row][col].begin(), bottomedges[row][col].end());//sort by first
		
		
			int rpntr = 0;
			int bpntr = 0;
			int rsz = rightedges[row][col].size();
			int bsz = bottomedges[row][col].size();
			
			
			set<int> vals;
			while(rpntr < rsz){
				while(bpntr < bsz and rightedges[row][col][rpntr].s >= bottomedges[row][col][bpntr].f){
					st.insert(bottomedges[row][col][bpntr].s + 1);
					vals.insert(bottomedges[row][col][bpntr].s + 1);
					//if(row == 1 and col == 1)
						//cout << bottomedges[row][col][bpntr].f <<", "<<bottomedges[row][col][bpntr].s<<endl;
					bpntr++;
				}
				
				ans += st.query(rightedges[row][col][rpntr].f +1);//number currently greater than thi
				/*if(row == 1 and col == 1){
					cout << rightedges[row][col][rpntr].s <<"; "<<rightedges[row][col][rpntr].f<<endl;
					cout <<rightedges[row][col][rpntr].f <<": "<< st.query(rightedges[row][col][rpntr].f +1)<<endl;
				}*/
				rpntr++;
			}
			
			auto it = vals.begin();
			while(it != vals.end()){
				st.erase(*it);
				it = vals.erase(it);
			}
	
			
		
			/*for(int r = 0; r < rightedges[row][col].size(); r++){
				for(int c =bottomedges[row][col].size() -1 ; c>=0 ; c--){
					if(row == 1 and col == 1){
						cout << rightedges[row][col][r].s<<", "<<rightedges[row][col][r].f<<":::";
						cout << bottomedges[row][col][c].f<<", "<<bottomedges[row][col][c].s<<endl;
					}
					if(rightedges[row][col][r].f <= bottomedges[row][col][c].s){
						if(rightedges[row][col][r].s >= bottomedges[row][col][c].f){
							ans++;
							//cout << row<<", "<<col<<": ";
							//cout << bottomedges[row][col][c].f<<", "<<bottomedges[row][col][c].s<<endl;
						}
					}
				}
			}*/
		}
	}


	
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:177:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |    for(int i =0; i<rightedges[row][col].size(); i++){
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
rect.cpp:184:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |    for(int i =0; i<bottomedges[row][col].size(); i++){
      |                  ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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