oj.uz

Submission #852982

# Submission time Handle Problem Language Result Execution time Memory
852982 2023-09-23T09:50:18 Z aykhn Horses (IOI15_horses) C++14
100 / 100
 960 ms 83496 KB 
#include "horses.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define fi first
#define se second
 
const ll mod = 1e9 + 7;
 
int n;
vector<ll> a, b;
set<ll> s;
multiset<ll> ms;
 
ll mult(ll a, ll b)
{
	return (a * b) % mod;
}
 
struct SegTree
{
	int sz;
	vector<ll> st;
	void build(int l, int r, int x)
	{
		if (l + 1 == r)
		{
			if (l < n) st[x] = mult(st[x], a[l]);
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, 2*x + 1);
		build(mid, r, 2*x + 2);
		st[x] = mult(st[2*x + 1], st[2*x + 2]);
	}
	void build(int n)
	{
		sz = 1;
		while (sz < n) sz <<= 1;
		st.assign(sz << 1, 1);
		build(0, sz, 0);
	}
	void make(int ind, ll val, int l, int r, int x)
	{
		if (l + 1 == r)
		{
			st[x] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if (ind < mid) make(ind, val, l, mid, 2*x + 1);
		else make(ind, val, mid, r, 2*x + 2);
		st[x] = mult(st[2*x + 1], st[2*x + 2]);
	}
	void make(int ind, ll val)
	{
		make(ind, val, 0, sz, 0);
	}
	ll get(int lx, int rx, int l, int r, int x)
	{
		if (l >= rx || r <= lx) return 1;
		if (l >= lx && r <= rx) return st[x];
		int mid = (l + r) >> 1;
		return mult(get(lx, rx, l, mid, 2*x + 1), get(lx, rx, mid, r, 2*x + 2));
	}
	ll get(int l, int r)
	{
		return get(l, r + 1, 0, sz, 0);
	}
};
struct SegTreeMX
{
	int sz;
	vector<ll> st;
	void build(int l, int r, int x)
	{
		if (l + 1 == r)
		{
			if (l < n) st[x] = b[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, 2*x + 1);
		build(mid, r, 2*x + 2);
		st[x] = max(st[2*x + 1], st[2*x + 2]);
	}
	void build(int n)
	{
		sz = 1;
		while (sz < n) sz <<= 1;
		st.assign(sz << 1, 1);
		build(0, sz, 0);
	}
	void make(int ind, ll val, int l, int r, int x)
	{
		if (l + 1 == r)
		{
			st[x] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if (ind < mid) make(ind, val, l, mid, 2*x + 1);
		else make(ind, val, mid, r, 2*x + 2);
		st[x] = max(st[2*x + 1], st[2*x + 2]);
	}
	void make(int ind, ll val)
	{
		make(ind, val, 0, sz, 0);
	}
	ll get(int lx, int rx, int l, int r, int x)
	{
		if (l >= rx || r <= lx) return 1;
		if (l >= lx && r <= rx) return st[x];
		int mid = (l + r) >> 1;
		return max(get(lx, rx, l, mid, 2*x + 1), get(lx, rx, mid, r, 2*x + 2));
	}
	ll get(int l, int r)
	{
		return get(l, r + 1, 0, sz, 0);
	}
};
 
SegTree st;
SegTreeMX stmx;
 
ll getans()
{
	ll ans = *ms.rbegin();
	if (s.empty()) return ans;
	vector<int> v;
	int k = 1;
	for (auto it = s.rbegin(); k <= 30 && it != s.rend(); it++, k++) v.pb(*it);
	reverse(all(v));
	ll mxb = stmx.get(v[0], (1 == v.size() ? n - 1 : v[1] - 1));
	ll x = 1;
	ll INF = 1e18;
	int f = 0;
	int ind = 0;
	for (int i = 1; i < v.size(); i++)
	{
		if (a[v[i]] >= INF/x) f = 1;
		if (!f) x *= a[v[i]];
		ll bb = stmx.get(v[i], (i + 1 == v.size() ? n - 1 : v[i + 1] - 1));
		if (!f && x >= INF/bb) f = 1;
		if (!f) x *= bb;
		if (f || x > mxb) 
		{
			ind = i;
			mxb = bb;
			f = 0;
			x = 1;
		}
		else x /= bb;
	}
	int szs = s.size();
	int szv = v.size();
	if (szs - (szv - ind) >= 30) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
	f = 0;
	x = 1;
	for (auto it = s.begin(); it != s.end() && *it <= v[ind]; it++)
	{
		if (a[*it] >= INF/x) f = 1;
		if (!f) x *= a[*it];
	}
	ll bb = stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1));
	if (bb >= INF/x) f = 1;
	if (!f) x *= bb;
	if (f || x > ans) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
	else return ans;
}
 
int init(int N, int X[], int Y[]) 
{
	n = N;
	for (int i = 0; i < N; i++) 
	{
		a.pb(X[i]), b.pb(Y[i]);
		if (X[i] > 1) s.ins(i);
		ms.ins(Y[i]);
	}
	st.build(n);
	stmx.build(n);
	return getans();
}
 
int updateX(int pos, int val) 
{	
	if (a[pos] > 1) s.erase(pos);
	a[pos] = val;
	if (a[pos] > 1) s.ins(pos);
	st.make(pos, val);
	return getans();
}
 
int updateY(int pos, int val) 
{
	ms.erase(ms.lower_bound(b[pos]));
	ms.ins(val);
	b[pos] = val;
	stmx.make(pos, val);
	return getans();
}

Compilation message

horses.cpp: In function 'll mult(ll, ll)':
horses.cpp:25:18: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   25 | ll mult(ll a, ll b)
      |               ~~~^
horses.cpp:21:15: note: shadowed declaration is here
   21 | vector<ll> a, b;
      |               ^
horses.cpp:25:12: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   25 | ll mult(ll a, ll b)
      |         ~~~^
horses.cpp:21:12: note: shadowed declaration is here
   21 | vector<ll> a, b;
      |            ^
horses.cpp: In member function 'void SegTree::build(int)':
horses.cpp:46:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   46 |  void build(int n)
      |             ~~~~^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int n;
      |     ^
horses.cpp: In member function 'void SegTreeMX::build(int)':
horses.cpp:97:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   97 |  void build(int n)
      |             ~~~~^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int n;
      |     ^
horses.cpp: In function 'll getans()':
horses.cpp:142:72: warning: conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
  142 |  for (auto it = s.rbegin(); k <= 30 && it != s.rend(); it++, k++) v.pb(*it);
      |                                                                        ^~~
horses.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |  for (int i = 1; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
horses.cpp:153:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   ll bb = stmx.get(v[i], (i + 1 == v.size() ? n - 1 : v[i + 1] - 1));
      |                           ~~~~~~^~~~~~~~~~~
horses.cpp:165:18: warning: conversion from 'std::set<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  165 |  int szs = s.size();
      |            ~~~~~~^~
horses.cpp:166:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  166 |  int szv = v.size();
      |            ~~~~~~^~
horses.cpp:167:88: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |  if (szs - (szv - ind) >= 30) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
      |                                                                                ~~~~~~~~^~~~~~~~~~~
horses.cpp:175:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |  ll bb = stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1));
      |                            ~~~~~~~~^~~~~~~~~~~
horses.cpp:178:77: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |  if (f || x > ans) return mult(st.get(0, v[ind]), stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1)));
      |                                                                     ~~~~~~~~^~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:193:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  193 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:202:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  202 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:211:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  211 |  return getans();
      |         ~~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 77524 KB Output is correct
2 Correct 650 ms 83496 KB Output is correct
3 Correct 653 ms 78412 KB Output is correct
4 Correct 948 ms 80708 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 3 ms 560 KB Output is correct
24 Correct 3 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 2 ms 348 KB Output is correct
27 Correct 3 ms 348 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 3 ms 604 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 3 ms 348 KB Output is correct
33 Correct 385 ms 52112 KB Output is correct
34 Correct 299 ms 54580 KB Output is correct
35 Correct 284 ms 81240 KB Output is correct
36 Correct 275 ms 81444 KB Output is correct
37 Correct 165 ms 53348 KB Output is correct
38 Correct 375 ms 65816 KB Output is correct
39 Correct 117 ms 53740 KB Output is correct
40 Correct 263 ms 78952 KB Output is correct
41 Correct 133 ms 53284 KB Output is correct
42 Correct 138 ms 53260 KB Output is correct
43 Correct 238 ms 78824 KB Output is correct
44 Correct 234 ms 78876 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 3 ms 344 KB Output is correct
25 Correct 3 ms 600 KB Output is correct
26 Correct 2 ms 348 KB Output is correct
27 Correct 3 ms 348 KB Output is correct
28 Correct 3 ms 572 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 3 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 4 ms 348 KB Output is correct
33 Correct 533 ms 77008 KB Output is correct
34 Correct 653 ms 83380 KB Output is correct
35 Correct 630 ms 78596 KB Output is correct
36 Correct 960 ms 80580 KB Output is correct
37 Correct 381 ms 54380 KB Output is correct
38 Correct 324 ms 55160 KB Output is correct
39 Correct 274 ms 81248 KB Output is correct
40 Correct 276 ms 81176 KB Output is correct
41 Correct 162 ms 53364 KB Output is correct
42 Correct 344 ms 65828 KB Output is correct
43 Correct 125 ms 53304 KB Output is correct
44 Correct 265 ms 78976 KB Output is correct
45 Correct 145 ms 53568 KB Output is correct
46 Correct 140 ms 53428 KB Output is correct
47 Correct 237 ms 78824 KB Output is correct
48 Correct 236 ms 78684 KB Output is correct
49 Correct 818 ms 56812 KB Output is correct
50 Correct 726 ms 56804 KB Output is correct
51 Correct 571 ms 82504 KB Output is correct
52 Correct 551 ms 82396 KB Output is correct
53 Correct 527 ms 56152 KB Output is correct
54 Correct 645 ms 69272 KB Output is correct
55 Correct 198 ms 53948 KB Output is correct
56 Correct 590 ms 80088 KB Output is correct
57 Correct 405 ms 54432 KB Output is correct
58 Correct 433 ms 54964 KB Output is correct
59 Correct 235 ms 75864 KB Output is correct