oj.uz

Submission #1076513

# Submission time Handle Problem Language Result Execution time Memory
1076513 2024-08-26T14:29:14 Z pcc Rectangles (IOI19_rect) C++17
10 / 100
 5000 ms 359120 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC target("avx2,popcnt,sse4")
#pragma GCC optimize("O3,unroll-loops")
#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long
#define _all(T) T.begin(),T.end()
#define tiii tuple<int,int,int>

const int mxn = 2520;
int N,M;
vector<vector<int>> arr;
vector<pii> row[mxn][mxn],col[mxn][mxn];

struct BIT{
	int bit[mxn];
	void modify(int p,int v){
		p++;
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int s,int e = -1){
		s++,e++;
		if(s>e)swap(s,e);
		int re = 0;
		for(;e>0;e-= e&-e)re += bit[e];
		s--;
		for(;s>0;s-= s&-s)re -= bit[s];
		return re;
	}
};

BIT bit;
ll calc(vector<pii> &v1,vector<pii> &v2){
	vector<tiii> v;
	ll re = 0;
	for(auto &i:v1)if(i.sc != -1)v.push_back(tiii(i.fs,0,i.sc));
	for(auto &i:v2)if(i.sc != -1)v.push_back(tiii(i.sc,1,i.fs));
	sort(v.begin(),v.end());
	for(auto [_,tp,pos]:v){
		if(tp == 0)bit.modify(pos,1);
		else re += bit.getval(pos,mxn-1);
	}
	for(auto [_,tp,pos]:v){
		bit.modify(pos,-bit.getval(pos,pos));
	}
	return re;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	N = a.size(),M = a[0].size();
	arr = a;

	{
		for(int i = 0;i<N;i++){
			vector<int> st;
			vector<pii> rng(M,pii(-1,-1));
			for(int j = 0;j<M;j++){
				while(!st.empty()&&arr[i][j]>=arr[i][st.back()])st.pop_back();
				if(!st.empty())rng[j].fs = st.back();
				st.push_back(j);
			}
			st.clear();
			for(int j = M-1;j>=0;j--){
				while(!st.empty()&&arr[i][j]>=arr[i][st.back()])st.pop_back();
				if(!st.empty())rng[j].sc = st.back();
				st.push_back(j);
			}
			for(int j = 0;j<M;j++){
				if(rng[j].fs != -1&&rng[j].sc != -1){
					row[i][rng[j].fs+1].push_back(pii(rng[j].sc-1,-1));
				}
			}
			cerr<<"ROW: "<<i<<":";for(auto &j:rng)cerr<<j.fs<<','<<j.sc<<' ';cerr<<endl;
		}
		for(int i = 0;i<M;i++){
			vector<int> st;
			vector<pii> rng(N,pii(-1,-1));
			for(int j = 0;j<N;j++){
				while(!st.empty()&&arr[st.back()][i]<=arr[j][i])st.pop_back();
				if(!st.empty())rng[j].fs = st.back();
				st.push_back(j);
			}
			st.clear();
			for(int j = N-1;j>=0;j--){
				while(!st.empty()&&arr[st.back()][i]<=arr[j][i])st.pop_back();
				if(!st.empty())rng[j].sc = st.back();
				st.push_back(j);
			}
			for(int j = 0;j<N;j++){
				if(rng[j].fs != -1&&rng[j].sc != -1){
					col[rng[j].fs+1][i].push_back(pii(rng[j].sc-1,-1));
				}
			}
			cerr<<"COL: "<<i<<":";for(auto &j:rng)cerr<<j.fs<<','<<j.sc<<' ';cerr<<endl;
		}
	}

	for(int i = 0;i<N;i++)for(int j = 0;j<M;j++){
		sort(_all(row[i][j]));
		sort(_all(col[i][j]));
	}

	{
		int nxt[mxn] = {};
		for(int i = 0;i<M;i++){
			memset(nxt,-1,sizeof(nxt));
			for(int j = 0;j<N;j++){
				for(auto &[tar,rp]:row[j][i]){
					if(nxt[tar]<j)nxt[tar] = j;
					auto tit = lower_bound(_all(row[j][i]),pii(tar,-1));
					while(nxt[tar]+1<N){
						int tmp = nxt[tar]+1;
						auto it = lower_bound(_all(row[tmp][i]),pii(tar,-1));
						if(it == row[tmp][i].end()||it->fs != tar)break;
						nxt[tar]++;
					}
					rp = nxt[tar];
				}
			}
		}

		for(int i = 0;i<N;i++){
			memset(nxt,-1,sizeof(nxt));
			for(int j = 0;j<M;j++){
				for(auto &[tar,rp]:col[i][j]){
					if(nxt[tar]<j)nxt[tar] = j;
					while(nxt[tar]+1<M){
						int tmp =  nxt[tar]+1;
						auto it = lower_bound(_all(col[i][tmp]),pii(tar,-1));
						if(it == col[i][tmp].end()||it->fs != tar)break;
						nxt[tar]++;
					}
					rp = nxt[tar];
				}
			}
		}

	}

	ll ans = 0;
	{
		for(int i = 0;i<N;i++){
			for(int j = 0;j<M;j++){
				cerr<<"CALC: "<<i<<','<<j<<endl;
				if(row[i][j].empty()||col[i][j].empty())continue;
				cerr<<"CALCING: "<<i<<','<<j<<endl;
				for(auto &k:row[i][j])cerr<<k.fs<<','<<k.sc<<' ';cerr<<endl;
				for(auto &k:col[i][j])cerr<<k.fs<<','<<k.sc<<' ';cerr<<endl;
				ans += calc(row[i][j],col[i][j]);
			}
		}
	}
	return ans;

}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:115:11: warning: variable 'tit' set but not used [-Wunused-but-set-variable]
  115 |      auto tit = lower_bound(_all(row[j][i]),pii(tar,-1));
      |           ^~~
rect.cpp:152:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  152 |     for(auto &k:row[i][j])cerr<<k.fs<<','<<k.sc<<' ';cerr<<endl;
      |     ^~~
rect.cpp:152:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  152 |     for(auto &k:row[i][j])cerr<<k.fs<<','<<k.sc<<' ';cerr<<endl;
      |                                                      ^~~~
rect.cpp:153:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  153 |     for(auto &k:col[i][j])cerr<<k.fs<<','<<k.sc<<' ';cerr<<endl;
      |     ^~~
rect.cpp:153:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  153 |     for(auto &k:col[i][j])cerr<<k.fs<<','<<k.sc<<' ';cerr<<endl;
      |                                                      ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 298576 KB Output is correct
2 Correct 144 ms 298580 KB Output is correct
3 Correct 142 ms 298748 KB Output is correct
4 Correct 189 ms 298620 KB Output is correct
5 Correct 132 ms 298580 KB Output is correct
6 Correct 143 ms 298576 KB Output is correct
7 Correct 131 ms 298612 KB Output is correct
8 Correct 131 ms 298504 KB Output is correct
9 Incorrect 137 ms 298576 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 298576 KB Output is correct
2 Correct 144 ms 298580 KB Output is correct
3 Correct 142 ms 298748 KB Output is correct
4 Correct 189 ms 298620 KB Output is correct
5 Correct 132 ms 298580 KB Output is correct
6 Correct 143 ms 298576 KB Output is correct
7 Correct 131 ms 298612 KB Output is correct
8 Correct 131 ms 298504 KB Output is correct
9 Incorrect 137 ms 298576 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 298576 KB Output is correct
2 Correct 144 ms 298580 KB Output is correct
3 Correct 142 ms 298748 KB Output is correct
4 Correct 189 ms 298620 KB Output is correct
5 Correct 132 ms 298580 KB Output is correct
6 Correct 143 ms 298576 KB Output is correct
7 Correct 131 ms 298612 KB Output is correct
8 Correct 131 ms 298504 KB Output is correct
9 Incorrect 137 ms 298576 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 298576 KB Output is correct
2 Correct 144 ms 298580 KB Output is correct
3 Correct 142 ms 298748 KB Output is correct
4 Correct 189 ms 298620 KB Output is correct
5 Correct 132 ms 298580 KB Output is correct
6 Correct 143 ms 298576 KB Output is correct
7 Correct 131 ms 298612 KB Output is correct
8 Correct 131 ms 298504 KB Output is correct
9 Incorrect 137 ms 298576 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 299456 KB Output is correct
2 Correct 245 ms 299088 KB Output is correct
3 Correct 221 ms 298876 KB Output is correct
4 Correct 128 ms 298580 KB Output is correct
5 Correct 253 ms 299232 KB Output is correct
6 Correct 244 ms 299092 KB Output is correct
7 Correct 250 ms 299092 KB Output is correct
8 Correct 236 ms 299084 KB Output is correct
9 Correct 243 ms 299220 KB Output is correct
10 Correct 182 ms 298836 KB Output is correct
11 Correct 212 ms 298832 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 298580 KB Output is correct
2 Execution timed out 5070 ms 359120 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 298576 KB Output is correct
2 Correct 144 ms 298580 KB Output is correct
3 Correct 142 ms 298748 KB Output is correct
4 Correct 189 ms 298620 KB Output is correct
5 Correct 132 ms 298580 KB Output is correct
6 Correct 143 ms 298576 KB Output is correct
7 Correct 131 ms 298612 KB Output is correct
8 Correct 131 ms 298504 KB Output is correct
9 Incorrect 137 ms 298576 KB Output isn't correct
10 Halted 0 ms 0 KB -