oj.uz

답안 #476324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476324 2021-09-26T03:41:14 Z MonkeyKing 3D Histogram (COCI20_histogram) C++14
110 / 110
 176 ms 4208 KB 
//Original Code:
//#include <self/utility>
//#include <self/debug>
//using namespace std;
//int n;
//int a[200005],b[200005];
//ll res;
//int tr[200005];
//int ma[200005],mb[200005];
//
//ll calc(int x,int y)
//{
//	return 1LL*min(ma[x],ma[y])*min(mb[x],mb[y])*(y-x+1);
//}
//
//void cdq1(int l,int r,int ql,int qr)
//{
//	if(l==r) return;
//	int md=l+r>>1;
//	ll res=-inf;
//	for(int i=ql;i<qr;i++)
//	{
//		ll v=calc(md,i);
//		if(v>=res)
//		{
//			res=v;
//			tr[md]=i;
//		}
//	}
//	chmax(::res,res);
//	cdq1(l,md,ql,tr[md]+1);
//	cdq1(md+1,r,tr[md],qr);
//}
//
//void cdq2(int l,int r,int ql,int qr)
//{
//	if(l==r) return;
//	int md=l+r>>1;
//	ll res=-inf;
//	for(int i=ql;i<qr;i++)
//	{
//		ll v=calc(md,i);
//		if(v>=res)
//		{
//			res=v;
//			tr[md]=i;
//		}
//	}
//	chmax(::res,res);
//	cdq2(l,md,tr[md],qr);
//	cdq2(md+1,r,ql,tr[md]+1);
//}
//
//void solve(int l,int r)
//{
//	if(r-l==1)
//	{
//		chmax(res,1LL*a[l]*b[l]);
//		return;
//	}
//	int md=l+r>>1;
//	for(int i=md-1;i>=l;i--)
//	{
//		ma[i]=min(i==md-1?inf:ma[i+1],a[i]);
//		mb[i]=min(i==md-1?inf:mb[i+1],b[i]);
//	}
//	for(int i=md;i<r;i++)
//	{
//		ma[i]=min(i==md?inf:ma[i-1],a[i]);
//		mb[i]=min(i==md?inf:mb[i-1],b[i]);
//	}
//	cdq1(l,md,md,r);
//	cdq2(l,md,md,r);
//	solve(l,md);
//	solve(md,r);
//}
//
//int main()
//{
//	// freopen("input.txt","r",stdin);
//	cin>>n;
//	for(int i=0;i<n;i++) scanf("%d%d",a+i,b+i);
//	solve(0,n);
//	cout<<res<<endl;
//	return 0;
//}

//substituted with C++ Inliner
#ifndef _SELF_UTILITY
#define _SELF_UTILITY 1
#include <numeric>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#include <time.h>
#define Endl endl
#define mp make_pair
#define mt make_tuple
#define ll long long 
#define ull unsigned long long
#define pii pair<int,int>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define quickcin ios_base::sync_with_stdio(false);
#ifdef __TAKE_MOD
int mod;
#else
#ifdef __TAKE_CONST_MOD
const int mod=__TAKE_CONST_MOD;
#else
const int mod=1000000007;
#endif
#endif
const int gmod=3;
const int inf=1039074182;
#ifdef __TAKE_CONST_EPS
const double eps=__TAKE_CONST_EPS;
#else
const double eps=1e-9;
#endif
const double pi=3.141592653589793238462643383279;
const ll llinf=2LL*inf*inf;
template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;}
template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;}
inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31 & mod);}
template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;}
template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;}
template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;}
template <typename T> inline T mabs(T x) {return (x<0?-x:x);}
using namespace std;
#endif
#ifndef _SELF_DEBUG
#define _SELF_DEBUG 1
#ifndef _SELF_OPERATOR
#define _SELF_OPERATOR 1
using namespace std;
template <typename T>
ostream & operator<<(ostream &cout, const vector<T> &vec)
{
	cout << "{";
	for (int i = 0; i < (int)vec.size(); i++)
	{
		cout << vec[i];
		if (i != (int)vec.size() - 1)
			cout << ',';
	}
	cout << "}";
	return cout;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &cout, pair<T1, T2> p)
{
	cout << "(" << p.first << ',' << p.second << ")";
	return cout;
}

template <typename T, typename T2>
ostream &operator<<(ostream &cout, set<T, T2> s)
{
	vector<T> t;
	for (auto x : s)
		t.push_back(x);
	cout << t;
	return cout;
}

template <typename T, typename T2>
ostream &operator<<(ostream &cout, multiset<T, T2> s)
{
	vector<T> t;
	for (auto x : s)
		t.push_back(x);
	cout << t;
	return cout;
}

template <typename T>
ostream &operator<<(ostream &cout, queue<T> q)
{
	vector<T> t;
	while (q.size())
	{
		t.push_back(q.front());
		q.pop();
	}
	cout << t;
	return cout;
}

template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &cout, map<T1, T2, T3> m)
{
	for (auto &x : m)
	{
		cout << "Key: " << x.first << ' ' << "Value: " << x.second << endl;
	}
	return cout;
}

template <typename T1, typename T2>
void operator+=(pair<T1, T2> &x,const pair<T1, T2> y)
{
	x.first += y.first;
	x.second += y.second;
}
template <typename T1,typename T2>
pair<T1,T2> operator + (const pair<T1,T2> &x,const pair<T1,T2> &y)
{
	return make_pair(x.first+y.first,x.second+y.second);
}

template <typename T1,typename T2>
pair<T1,T2> operator - (const pair<T1,T2> &x,const pair<T1,T2> &y)
{
	return mp(x.first-y.first,x.second-y.second);
}

template <typename T1, typename T2>
pair<T1, T2> operator-(pair<T1, T2> x)
{
	return make_pair(-x.first, -x.second);
}

template <typename T>
vector<vector<T>> operator~(vector<vector<T>> vec)
{
	vector<vector<T>> v;
	int n = vec.size(), m = vec[0].size();
	v.resize(m);
	for (int i = 0; i < m; i++)
	{
		v[i].resize(n);
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			v[i][j] = vec[j][i];
		}
	}
	return v;
}
#endif
#include <sstream>
void print0x(int x)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	std::reverse(vec.begin(),vec.end());
	for(int i=0;i<(int)vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}

template <typename T>
void print0x(T x,int len)
{
	std::vector <int> vec;
	while(x)
	{
		std::cout<<(x&1);
		x>>=1;
		len--;
		// vec.push_back(x&1);
		// x>>=1;
	}
	while(len--) cout<<0;
	// reverse(vec.begin(),vec.end());
	// for(int i=(int)vec.size();i<len;i++)
	// {
	// 	putchar('0');
	// }
	// for(size_t i=0;i<vec.size();i++)
	// {
	// 	std::cout<<vec[i];
	// }
	// std::cout<<' ';
}
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#endif
using namespace std;
int n;
int a[200005],b[200005];
ll res;
int tr[200005];
int ma[200005],mb[200005];

ll calc(int x,int y)
{
	return 1LL*min(ma[x],ma[y])*min(mb[x],mb[y])*(y-x+1);
}

void cdq1(int l,int r,int ql,int qr)
{
	if(l==r) return;
	int md=l+r>>1;
	ll res=-inf;
	for(int i=ql;i<qr;i++)
	{
		ll v=calc(md,i);
		if(v>=res)
		{
			res=v;
			tr[md]=i;
		}
	}
	chmax(::res,res);
	cdq1(l,md,ql,tr[md]+1);
	cdq1(md+1,r,tr[md],qr);
}

void cdq2(int l,int r,int ql,int qr)
{
	if(l==r) return;
	int md=l+r>>1;
	ll res=-inf;
	for(int i=ql;i<qr;i++)
	{
		ll v=calc(md,i);
		if(v>=res)
		{
			res=v;
			tr[md]=i;
		}
	}
	chmax(::res,res);
	cdq2(l,md,tr[md],qr);
	cdq2(md+1,r,ql,tr[md]+1);
}

void solve(int l,int r)
{
	if(r-l==1)
	{
		chmax(res,1LL*a[l]*b[l]);
		return;
	}
	int md=l+r>>1;
	for(int i=md-1;i>=l;i--)
	{
		ma[i]=min(i==md-1?inf:ma[i+1],a[i]);
		mb[i]=min(i==md-1?inf:mb[i+1],b[i]);
	}
	for(int i=md;i<r;i++)
	{
		ma[i]=min(i==md?inf:ma[i-1],a[i]);
		mb[i]=min(i==md?inf:mb[i-1],b[i]);
	}
	cdq1(l,md,md,r);
	cdq2(l,md,md,r);
	solve(l,md);
	solve(md,r);
}

int main()
{
//	// freopen("input.txt","r",stdin);
	cin>>n;
	for(int i=0;i<n;i++) scanf("%d%d",a+i,b+i);
	solve(0,n);
	cout<<res<<endl;
	return 0;
}

Compilation message

histogram.cpp: In function 'void cdq1(int, int, int, int)':
histogram.cpp:334:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  334 |  int md=l+r>>1;
      |         ~^~
histogram.cpp: In function 'void cdq2(int, int, int, int)':
histogram.cpp:353:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  353 |  int md=l+r>>1;
      |         ~^~
histogram.cpp: In function 'void solve(int, int)':
histogram.cpp:376:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  376 |  int md=l+r>>1;
      |         ~^~
histogram.cpp: In function 'int main()':
histogram.cpp:397:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  397 |  for(int i=0;i<n;i++) scanf("%d%d",a+i,b+i);
      |                       ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 332 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 138 ms 4184 KB Output is correct
14 Correct 168 ms 4064 KB Output is correct
15 Correct 124 ms 4160 KB Output is correct
16 Correct 148 ms 4176 KB Output is correct
17 Correct 164 ms 4192 KB Output is correct
18 Correct 128 ms 4176 KB Output is correct
19 Correct 122 ms 4184 KB Output is correct
20 Correct 150 ms 4208 KB Output is correct
21 Correct 130 ms 4144 KB Output is correct
22 Correct 176 ms 4156 KB Output is correct
23 Correct 18 ms 588 KB Output is correct
24 Correct 136 ms 4136 KB Output is correct