oj.uz

Submission #1034426

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

struct fenwick{
	long long fn[maxn];
	vector<long long>allind;
	void clear(){
		for(auto x:allind){
			while(x<maxn){
				fn[x]=0;
				x+=((-x)&x);
			}
		}
		allind.clear();
	}
	void add(long long i,long long w){
		i++;
		allind.push_back(i);
		while(i<maxn){
			fn[i]+=w;
			i+=((-i)&i);
		}
	}
	long long pors(long long l,long long r){
		long long 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(long long i=1;i<=n;i++){
		vector<pair<long long,long long>>allv;
		for(long long j=1;j<=m;j++){
			while((long long)allv.size()>0&&allv.back().first<=all[i][j]){
				alll[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((long long)allv.size()>0){
				alll[i][j].push_back(allv.back().second);
			}
			allv.push_back(make_pair(all[i][j],j));
		}
	}
	for(long long j=1;j<=m;j++){
		vector<pair<long long,long long>>allv;
		for(long long i=n;i>=1;i--){
			while((long long)allv.size()>0&&allv.back().first<=all[i][j]){
				alld[i][j].push_back(allv.back().second);
				allv.pop_back();
			}
			if((long long)allv.size()>0){
				alld[i][j].push_back(allv.back().second);
			}
			allv.push_back(make_pair(all[i][j],i));
		}
	}
}

void solveq(){
	for(long long i=1;i<=n;i++){
		for(long long 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((long long)addy[i][j].size()>0&&(long long)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((long long)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(long long i=1;i<=n;i++){
		for(long long 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(long long j=1;j<=m;j++){
			for(auto x:alld[i][j]){
				if(x<=i+1){
					continue;
				}
				dpp[x][j]=0;
			}
		}
	}
	for(long long j=1;j<=m;j++){
		for(long long 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(long long 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(long long i=1;i<=n;i++){
		for(long long 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 234 ms 592088 KB Output is correct
2 Correct 221 ms 592464 KB Output is correct
3 Correct 269 ms 592468 KB Output is correct
4 Correct 212 ms 592464 KB Output is correct
5 Correct 222 ms 592264 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 220 ms 592492 KB Output is correct
8 Correct 237 ms 592244 KB Output is correct
9 Incorrect 222 ms 592464 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 592088 KB Output is correct
2 Correct 221 ms 592464 KB Output is correct
3 Correct 269 ms 592468 KB Output is correct
4 Correct 212 ms 592464 KB Output is correct
5 Correct 222 ms 592264 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 220 ms 592492 KB Output is correct
8 Correct 237 ms 592244 KB Output is correct
9 Incorrect 222 ms 592464 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 592088 KB Output is correct
2 Correct 221 ms 592464 KB Output is correct
3 Correct 269 ms 592468 KB Output is correct
4 Correct 212 ms 592464 KB Output is correct
5 Correct 222 ms 592264 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 220 ms 592492 KB Output is correct
8 Correct 237 ms 592244 KB Output is correct
9 Incorrect 222 ms 592464 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 592088 KB Output is correct
2 Correct 221 ms 592464 KB Output is correct
3 Correct 269 ms 592468 KB Output is correct
4 Correct 212 ms 592464 KB Output is correct
5 Correct 222 ms 592264 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 220 ms 592492 KB Output is correct
8 Correct 237 ms 592244 KB Output is correct
9 Incorrect 222 ms 592464 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 593236 KB Output is correct
2 Correct 220 ms 593064 KB Output is correct
3 Correct 273 ms 592628 KB Output is correct
4 Correct 244 ms 592212 KB Output is correct
5 Correct 224 ms 593104 KB Output is correct
6 Correct 219 ms 592988 KB Output is correct
7 Correct 253 ms 593096 KB Output is correct
8 Correct 232 ms 592976 KB Output is correct
9 Incorrect 243 ms 593000 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 592088 KB Output is correct
2 Correct 221 ms 592464 KB Output is correct
3 Correct 269 ms 592468 KB Output is correct
4 Correct 212 ms 592464 KB Output is correct
5 Correct 222 ms 592264 KB Output is correct
6 Correct 225 ms 592468 KB Output is correct
7 Correct 220 ms 592492 KB Output is correct
8 Correct 237 ms 592244 KB Output is correct
9 Incorrect 222 ms 592464 KB Output isn't correct
10 Halted 0 ms 0 KB -