oj.uz

Submission #392876

# Submission time Handle Problem Language Result Execution time Memory
392876 2021-04-22T05:27:52 Z arwaeystoamneg Horses (IOI15_horses) C++17
100 / 100
 1146 ms 57148 KB 
// 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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 3 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 9 ms 332 KB Output is correct
28 Correct 4 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 6 ms 368 KB Output is correct
32 Correct 8 ms 324 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 45532 KB Output is correct
2 Correct 374 ms 57128 KB Output is correct
3 Correct 425 ms 48372 KB Output is correct
4 Correct 530 ms 52344 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 324 KB Output is correct
25 Correct 3 ms 332 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 9 ms 332 KB Output is correct
28 Correct 4 ms 324 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 6 ms 332 KB Output is correct
32 Correct 8 ms 332 KB Output is correct
33 Correct 54 ms 20112 KB Output is correct
34 Correct 48 ms 20112 KB Output is correct
35 Correct 220 ms 56464 KB Output is correct
36 Correct 199 ms 56532 KB Output is correct
37 Correct 139 ms 18312 KB Output is correct
38 Correct 129 ms 32884 KB Output is correct
39 Correct 41 ms 18304 KB Output is correct
40 Correct 182 ms 51468 KB Output is correct
41 Correct 94 ms 18184 KB Output is correct
42 Correct 120 ms 18252 KB Output is correct
43 Correct 171 ms 51948 KB Output is correct
44 Correct 178 ms 51940 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 3 ms 332 KB Output is correct
26 Correct 2 ms 344 KB Output is correct
27 Correct 8 ms 332 KB Output is correct
28 Correct 4 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 6 ms 332 KB Output is correct
32 Correct 9 ms 332 KB Output is correct
33 Correct 1146 ms 48384 KB Output is correct
34 Correct 370 ms 57148 KB Output is correct
35 Correct 418 ms 48404 KB Output is correct
36 Correct 523 ms 52196 KB Output is correct
37 Correct 51 ms 20164 KB Output is correct
38 Correct 47 ms 20100 KB Output is correct
39 Correct 213 ms 56360 KB Output is correct
40 Correct 198 ms 56420 KB Output is correct
41 Correct 137 ms 18380 KB Output is correct
42 Correct 127 ms 32928 KB Output is correct
43 Correct 39 ms 18252 KB Output is correct
44 Correct 184 ms 51412 KB Output is correct
45 Correct 93 ms 18252 KB Output is correct
46 Correct 119 ms 18344 KB Output is correct
47 Correct 172 ms 51916 KB Output is correct
48 Correct 174 ms 51872 KB Output is correct
49 Correct 197 ms 20200 KB Output is correct
50 Correct 154 ms 20212 KB Output is correct
51 Correct 444 ms 56572 KB Output is correct
52 Correct 295 ms 56584 KB Output is correct
53 Correct 1112 ms 18372 KB Output is correct
54 Correct 450 ms 36024 KB Output is correct
55 Correct 176 ms 18312 KB Output is correct
56 Correct 294 ms 51616 KB Output is correct
57 Correct 707 ms 18380 KB Output is correct
58 Correct 985 ms 18372 KB Output is correct
59 Correct 168 ms 51972 KB Output is correct