Submission #841860

#	Time	Username	Problem	Language	Result	Execution time	Memory
841860		TheLostCookie	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	4510 ms	80876 KiB

soccer

#include "soccer.h"
#include <algorithm>
#include <set>
#include <tuple>

struct DCSet {
	int n;
	std::vector<std::multiset<std::tuple<int,int,int,int>>> s;
	
	DCSet(int n): n(n), s(4*n) {
		
	}
	
	void insert(const std::tuple<int,int,int,int> &e) {
		insert(e,0,0,n-1);
	}
	
	void erase(const std::tuple<int,int,int,int> &e) {
		erase(e,0,0,n-1);
	}
	
	std::vector<std::tuple<int,int,int,int>> get(int p) {
		std::vector<std::tuple<int,int,int,int>> ret;
		int u=0,l=0,r=n-1;
		while(r-l) {
			for(auto e: s[u]) ret.push_back(e);
			int m = (l+r+1)/2;
			if(p<=m-1) u=2*u+1,r=m-1;
			else u=2*u+2,l=m;
		}
		for(auto e: s[u]) ret.push_back(e);
		
		return ret;
	}
	
private:
	void insert(const std::tuple<int,int,int,int> &e, int u, int l, int r) {
		auto [l0,r0,i,j] = e;
		if(l0 <= l && r <= r0) {
			s[u].insert(e);
		} else if(r-l>=1) {
			int m = (l+r+1)/2;
			if(l0 <= m-1) insert(e,2*u+1,l,m-1);
			if(m <= r0) insert(e,2*u+2,m,r);
		}
	}
	void erase(const std::tuple<int,int,int,int> &e, int u, int l, int r) {
		auto [l0,r0,i,j] = e;
		if(l0 <= l && r <= r0) {
			s[u].erase(s[u].find(e));
		} else if(r-l>=1) {
			int m = (l+r+1)/2;
			if(l0 <= m-1) erase(e,2*u+1,l,m-1);
			if(m <= r0) erase(e,2*u+2,m,r);
		}
	}
};

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
	auto solveDirection = [&N](std::vector<std::vector<int>> g)->std::vector<std::vector<int>> {		
		std::vector<std::vector<int>> d(N+1,std::vector<int>(N+1,0));
		DCSet s(N);
		
		auto split = [&d,&s](int row, int p) {
			auto pIntervals = s.get(p);
			for(auto e: pIntervals) {
				auto [l,r,i,j] = e;
				d[i][l] += (r-l+1)*(row-j);
				d[i][r+1] -= (r-l+1)*(row-j);
				s.erase(e);
				if(l<p) {
					s.insert(std::make_tuple(l,p-1,i,row));
				}
				if(p<r) {
					s.insert(std::make_tuple(p+1,r,i,row));
				}
			}
			return;
		};
		
		for(int i = 0; i < N; i++) {
			//Insert new elements;
			/*for(int l=0,r; l<N; l=r+1) {
				if(!g[i][l]) {
					r=l;
					while(r<N-1&&!g[i][r+1]) r++;
					s.insert(std::make_tuple(l,r,i,i));
				} else r=l;
			}*/
			s.insert(std::make_tuple(0,N-1,i,i));
			
			//Split intervals
			for(int j = 0; j < N; j++) {
				if(g[i][j]) split(i,j);
			}			
		}
		
		//Handle remaining elements
		for(int j = 0; j < N; j++) {
			split(N,j);
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				d[i][j+1] += d[i][j];
			}
			d[i].pop_back();
		}
		d.pop_back();
	
		return d;
	};
	
	auto down = solveDirection(F);
	std::reverse(F.begin(),F.end());
	auto up = solveDirection(F);
	std::reverse(F.begin(),F.end());
	std::reverse(up.begin(),up.end());
	
	int ans = 0;
	for(int i = 0; i < N; i++) {
		std::vector<int> prv(N);
		std::vector<int> nxt(N);
		for(int j = 0; j < N; j++) {
			prv[j] = (F[i][j]?j:(j==0?-1:prv[j-1]));
		}
		for(int j = N-1; j >= 0; j--) {
			nxt[j] = (F[i][j]?j:(j==N-1?N:nxt[j+1]));
		}
		for(int j = 0; j < N; j++) {
			if(!F[i][j]) ans = std::max(ans,down[i][j]+up[i][j]-(nxt[j]-prv[j]-1));
		}
	}
	
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30