oj.uz

Submission #1034422

# Submission time Handle Problem Language Result Execution time Memory
1034422 2024-07-25T13:39:38 Z amirhoseinfar1385 Rectangles (IOI19_rect) C++17
0 / 100
 257 ms 593272 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2500+10,ted=8;
int all[maxn][maxn],vis[maxn][maxn],tp[maxn][maxn],n,m,dpp[maxn][maxn],dpd[maxn][maxn];
vector<int>alll[maxn][maxn],alld[maxn][maxn];
vector<pair<int,pair<int,int>>>allq[maxn][maxn];
vector<pair<int,int>>addy[maxn][maxn];
long long mainres=0;

struct fenwick{
	int fn[maxn];
	vector<int>allind;
	void clear(){
		for(auto x:allind){
			while(x<maxn){
				fn[x]=0;
				x+=((-x)&x);
			}
		}
		allind.clear();
	}
	void add(int i,int w){
		i++;
		allind.push_back(i);
		while(i<maxn){
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	int pors(int l,int r){
		int ret=0;
		r++;
		while(l>0){
			ret-=fn[l];
			l-=((-l)&l);
		}
		while(r>0){
			ret+=fn[r];
			r-=((-r)&r);
		}
		return ret;
	}
}fen;


void pre(){
	for(int i=1;i<=n;i++){
		vector<pair<int,int>>allv;
		for(int j=1;j<=m;j++){
			while((int)allv.size()>0&&allv.back().first<all[i][j]){
				alll[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((int)allv.size()>0){
				alll[i][j].push_back(allv.back().second);
			}
			allv.push_back(make_pair(all[i][j],j));
		}
	}
	for(int j=1;j<=m;j++){
		vector<pair<int,int>>allv;
		for(int i=n;i>=1;i--){
			while((int)allv.size()>0&&allv.back().first<all[i][j]){
				alld[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((int)allv.size()>0){
				alld[i][j].push_back(allv.back().second);
			}
			allv.push_back(make_pair(all[i][j],i));
		}
	}
}

void solveq(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			sort(addy[i][j].begin(),addy[i][j].end());
			sort(allq[i][j].begin(),allq[i][j].end());
	//		cout<<i<<" "<<j<<" :"<<endl;
	//		for(auto x:addy[i][j]){
	//			cout<<x.first<<" "<<x.second<<endl;
	//		}
	//		for(auto x:allq[i][j]){
	//			cout<<x.first<<" "<<x.second.first<<" "<<x.second.second<<endl;
	//		}
			while((int)addy[i][j].size()>0&&(int)allq[i][j].size()>0){
				if(addy[i][j].back().first>=allq[i][j].back().first){
					fen.add(addy[i][j].back().second,1);
					addy[i][j].pop_back();
				}else{
					mainres+=fen.pors(allq[i][j].back().second.first,allq[i][j].back().second.second);
					allq[i][j].pop_back();
				}
			}
			while((int)allq[i][j].size()>0){
				mainres+=fen.pors(allq[i][j].back().second.first,allq[i][j].back().second.second);
				allq[i][j].pop_back();
			}
			fen.clear();
		}
	}
}

void calq(){
	for(int i=0;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(auto x:alld[i][j]){
				if(x<=i+1){
					continue;
				}
				dpp[x][j]=dpp[x][j-1]+1;
				allq[i+1][j+1].push_back(make_pair((x-i-1),make_pair(j-dpp[x][j],j-1)));
			}
		}
		for(int j=1;j<=m;j++){
			for(auto x:alld[i][j]){
				if(x<=i+1){
					continue;
				}
				dpp[x][j]=0;
			}
		}
	}
	for(int j=1;j<=m;j++){
		for(int i=n;i>=1;i--){
			for(auto x:alll[i][j]){
				if(x+1>=j){
					continue;
				}
				dpp[i][x]=dpp[i+1][x]+1;
				addy[i][j].push_back(make_pair(dpp[i][x],x));
			}
		}
		for(int i=n;i>=1;i--){
			for(auto x:alll[i][j]){
				if(x+1>=j){
					continue;
				}
				dpp[i][x]=0;
			}
		}
	}
}

void solve(){
	pre();
	calq();
	solveq();
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size();
	m=a[0].size();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			all[i][j]=a[i-1][j-1];
		}
	}
	solve();
	return mainres;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 592208 KB Output is correct
2 Correct 233 ms 592668 KB Output is correct
3 Correct 227 ms 592468 KB Output is correct
4 Correct 220 ms 592464 KB Output is correct
5 Correct 231 ms 592208 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 225 ms 592472 KB Output is correct
8 Correct 220 ms 592300 KB Output is correct
9 Incorrect 233 ms 592468 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 592208 KB Output is correct
2 Correct 233 ms 592668 KB Output is correct
3 Correct 227 ms 592468 KB Output is correct
4 Correct 220 ms 592464 KB Output is correct
5 Correct 231 ms 592208 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 225 ms 592472 KB Output is correct
8 Correct 220 ms 592300 KB Output is correct
9 Incorrect 233 ms 592468 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 592208 KB Output is correct
2 Correct 233 ms 592668 KB Output is correct
3 Correct 227 ms 592468 KB Output is correct
4 Correct 220 ms 592464 KB Output is correct
5 Correct 231 ms 592208 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 225 ms 592472 KB Output is correct
8 Correct 220 ms 592300 KB Output is correct
9 Incorrect 233 ms 592468 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 592208 KB Output is correct
2 Correct 233 ms 592668 KB Output is correct
3 Correct 227 ms 592468 KB Output is correct
4 Correct 220 ms 592464 KB Output is correct
5 Correct 231 ms 592208 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 225 ms 592472 KB Output is correct
8 Correct 220 ms 592300 KB Output is correct
9 Incorrect 233 ms 592468 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 593272 KB Output is correct
2 Correct 239 ms 592724 KB Output is correct
3 Correct 257 ms 592724 KB Output is correct
4 Correct 226 ms 592136 KB Output is correct
5 Correct 227 ms 592976 KB Output is correct
6 Correct 225 ms 592980 KB Output is correct
7 Correct 226 ms 592876 KB Output is correct
8 Correct 224 ms 592720 KB Output is correct
9 Incorrect 219 ms 592976 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 592212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 592208 KB Output is correct
2 Correct 233 ms 592668 KB Output is correct
3 Correct 227 ms 592468 KB Output is correct
4 Correct 220 ms 592464 KB Output is correct
5 Correct 231 ms 592208 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 225 ms 592472 KB Output is correct
8 Correct 220 ms 592300 KB Output is correct
9 Incorrect 233 ms 592468 KB Output isn't correct
10 Halted 0 ms 0 KB -