Submission #392876

#	Time	Username	Problem	Language	Result	Execution time	Memory
392876		arwaeystoamneg	Horses (IOI15_horses)	C++17	100 / 100	1146 ms	57148 KiB

horses

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}

template<int MOD, int RT> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; } // primitive root for FFT
	int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
	mint() { v = 0; }
	mint(ll _v) {
		v = int((-MOD < _v&& _v < MOD) ? _v : _v % MOD);
		if (v < 0) v += MOD;
	}
	friend bool operator==(const mint& a, const mint& b) {
		return a.v == b.v;
	}
	friend bool operator!=(const mint& a, const mint& b) {
		return !(a == b);
	}
	friend bool operator<(const mint& a, const mint& b) {
		return a.v < b.v;
	}

	mint& operator+=(const mint& m) {
		if ((v += m.v) >= MOD) v -= MOD;
		return *this;
	}
	mint& operator-=(const mint& m) {
		if ((v -= m.v) < 0) v += MOD;
		return *this;
	}
	mint& operator*=(const mint& m) {
		v = int((ll)v * m.v % MOD); return *this;
	}
	mint& operator/=(const mint& m) { return (*this) *= inv(m); }
	friend mint power(mint a, ll p) {// MAKE SURE YOU ARE USING THE CORRECT VERSION OF POW!!!!!!!!
		mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	friend mint inv(const mint& a) {
		assert(a.v != 0);
		return power(a, MOD - 2);
	}

	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this += 1; }
	mint& operator--() { return *this -= 1; }
	friend mint operator+(mint a, const mint& b) { return a += b; }
	friend mint operator-(mint a, const mint& b) { return a -= b; }
	friend mint operator*(mint a, const mint& b) { return a *= b; }
	friend mint operator/(mint a, const mint& b) { return a /= b; }
};
template<class T>class segment_tree
{
	struct item
	{
		T sum;
	};
	item single(T i)
	{
		return { i };
	}
	item merge(item x, item y)
	{
		item ans;
		ans.sum = max(x.sum, y.sum);
		return ans;
	}
	vector<item> tree;
	vector<item>A;
	int height;
	item neutral = { 0 };
public:void build(vector<T>& B)
{
	int	n = B.size();
	height = log2(n + 1) + 1;
	A.rsz(n);
	tree.rsz((1 << height + 1) - 1);
	F0R(i, n)A[i] = single(B[i]);
	A.rsz(1 << height, neutral);
	build(A, 0, 0, (1 << height) - 1);
}
	  void build(vector<item>& A, int v, int tl, int tr)
	  {
		  if (tl == tr)
			  tree[v] = A[tl];
		  else
		  {
			  int mid = (tl + tr) / 2;
			  build(A, 2 * v + 1, tl, mid);
			  build(A, 2 * v + 2, mid + 1, tr);
			  tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		  }
	  }
public:T query(int l, int r)
{
	return query(0, 0, (1 << height) - 1, l, r).sum;
}
	  item query(int v, int tl, int tr, int l, int r)
	  {
		  if (r<tl || l>tr)return neutral;
		  if (l <= tl && r >= tr)
		  {
			  return tree[v];
		  }
		  int mid = (tl + tr) / 2;
		  return merge(query(2 * v + 1, tl, mid, l, r), query(2 * v + 2, mid + 1, tr, l, r));
	  }
	  //assign
public:void update(int pos, T val)
{
	update(0, 0, (1 << height) - 1, pos, single(val));
}
	  void update(int v, int tl, int tr, int pos, item val)
	  {
		  if (tl == tr)
		  {
			  tree[v] = val;
		  }
		  else
		  {
			  int mid = (tl + tr) / 2;
			  if (pos <= mid)
				  update(2 * v + 1, tl, mid, pos, val);
			  else
				  update(2 * v + 2, mid + 1, tr, pos, val);
			  tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		  }
	  }
};
typedef mint<inf, 5> mi;
#ifndef arwaeystoamneg
#include "horses.h"
#endif
const int MAX_N = 500005, MAX_V = 1000000000;
int n, a[MAX_N];
segment_tree<int>best;
mi prod;
struct T
{
	int x;
	int l, r;
};
map<int, T>active;
int query()
{
	auto it = active.end();
	pair<ll, int>ans = { -MAX_V,-1 };
	ll cur = 1;
	mi t = prod;
	while (it != active.begin())
	{
		it--;
		t *= inv((mi)it->s.x);
		cur *= it->s.x;
		if (cur > MAX_V)
		{
			t *= it->s.x;
			it++;
			break;
		}
	}
	cur = 1;
	auto prev = it;
	if (prev != active.begin())
	{
		prev--;
		int v = best.query(prev->s.l, prev->s.r);
		ans = max(ans, { cur * v,(int)(t * v) });
	}
	while (it != active.end())
	{
		int v = best.query(it->s.l, it->s.r);
		t *= it->s.x;
		cur *= it->s.x;
		ans = max(ans, { cur * v ,(int)(t * v) });
		it++;
	}
	return ans.s;
}
int init(int N, int X[], int Y[]) 
{
	n = N;
	F0R(i, n)a[i] = X[i];
	vi t(n);
	F0R(i, n)t[i] = Y[i];
	best.build(t);
	prod = 1;
	F0R(i, n)prod *= X[i];
	int last = 0;
	FOR(i, 1, n)
	{
		if (X[i] == 1)
		{

		}
		else
		{
			active.insert({ last,{X[last],last,i - 1} });
			last = i;
		}
	}
	active.insert({ last,{X[last],last,n - 1} });
	return query();
}

int updateX(int pos, int val) 
{
	if (val == 1)
	{
		if (a[pos] == 1)
		{

		}
		else if (pos == 0)
		{
			active.begin()->s.x = 1;
		}
		else
		{
			auto it = active.find(pos);
			int r = it->s.r;
			it--;
			it->s.r = r;
			it++;
			active.erase(it);
		}
	}
	else
	{
		if (a[pos] == 1 && pos)
		{
			// 0 is always in active so there will always be a --
			auto it = active.upper_bound(pos);
			it--;
			int r = it->s.r;//  please
			it->s.r = pos - 1;// dont be the only reason why this was wrong
			active.insert({ pos, {val,pos,r} });
		}
		else
		{
			active[pos].x = val;
		}
	}
	prod *= inv((mi)a[pos]);
	prod *= val;
	a[pos] = val;
	return query();
}

int updateY(int pos, int val) 
{
	best.update(pos, val);
	return query();
}


#ifdef arwaeystoamneg




int main() {
	setIO("test1");

	int N; 
	cin >> N;

	int* X = (int*)malloc(sizeof(int) * (unsigned int)N);
	int* Y = (int*)malloc(sizeof(int) * (unsigned int)N);

	for (int i = 0; i < N; i++) {
		cin >> X[i];
	}

	for (int i = 0; i < N; i++) {
		cin >> Y[i];
	}

	cout << init(N, X, Y) << endl;

	int M; 
	cin >> M;

	for (int i = 0; i < M; i++) {
		int type; 
		int pos; 
		int val; 
		cin >> type >> pos >> val;
		if (type == 1) {
			cout << updateX(pos, val) << endl;
		}
		else if (type == 2) {
			cout << updateY(pos, val) << endl;
		}
	}

	return 0;
}

#endif

Compilation message (stderr)

horses.cpp: In member function 'void segment_tree<T>::build(std::vector<segment_tree<T>::item>&, int, int, int)':
horses.cpp:134:4: warning: declaration of 'A' shadows a member of 'segment_tree<T>' [-Wshadow]
  134 |    {
      |    ^
horses.cpp:120:14: note: shadowed declaration is here
  120 |  vector<item>A;
      |              ^
horses.cpp: In instantiation of 'void segment_tree<T>::build(std::vector<_Tp>&) [with T = int]':
horses.cpp:237:14:   required from here
horses.cpp:125:6: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  125 |  int n = B.size();
      |      ^
horses.cpp:126:23: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'int' may change value [-Wfloat-conversion]
  126 |  height = log2(n + 1) + 1;
      |           ~~~~~~~~~~~~^~~
horses.cpp:128:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  128 |  tree.rsz((1 << height + 1) - 1);
      |                 ~~~~~~~^~~
horses.cpp: In instantiation of 'void segment_tree<T>::build(std::vector<segment_tree<T>::item>&, int, int, int) [with T = int]':
horses.cpp:131:2:   required from 'void segment_tree<T>::build(std::vector<_Tp>&) [with T = int]'
horses.cpp:237:14:   required from here
horses.cpp:133:9: warning: declaration of 'A' shadows a member of 'segment_tree<int>' [-Wshadow]
  133 |    void build(vector<item>& A, int v, int tl, int tr)
      |         ^~~~~
horses.cpp:120:14: note: shadowed declaration is here
  120 |  vector<item>A;
      |              ^
horses.cpp: In function 'void setIO(std::string)':
horses.cpp:48:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:50:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   50 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23