oj.uz

Submission #852970

# Submission time Handle Problem Language Result Execution time Memory
852970 2023-09-23T09:30:02 Z aykhn Horses (IOI15_horses) C++14
17 / 100
 582 ms 107700 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, 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++) 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) 
{	
	a[pos] = val;
	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();
}

// ans will always be max i such that P [1, i] * y[i] is max
// comparing 2 answers (i < j)

// P[1, i] * y[i] < P[1, j] * y[j];
// y[i] < P[1, j] * y[j] / P[1, i];
// y[i] < y[j] * P[i + 1, j];
// if (num>1(j - i) + (y[j] > 1) >= 30) true;
// else calculate

Compilation message

horses.cpp: In function 'll mult(ll, ll)':
horses.cpp:24:18: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   24 | ll mult(ll a, ll b)
      |               ~~~^
horses.cpp:21:15: note: shadowed declaration is here
   21 | vector<ll> a, b;
      |               ^
horses.cpp:24:12: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   24 | 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:45:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   45 |  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:96:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   96 |  void build(int n)
      |             ~~~~^
horses.cpp:20:5: note: shadowed declaration is here
   20 | int n;
      |     ^
horses.cpp: In function 'll getans()':
horses.cpp:141:67: warning: conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
  141 |  for (auto it = s.rbegin(); k <= 30 && it != s.rend(); it++) v.pb(*it);
      |                                                                   ^~~
horses.cpp:148:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |  for (int i = 1; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
horses.cpp:152:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   ll bb = stmx.get(v[i], (i + 1 == v.size() ? n - 1 : v[i + 1] - 1));
      |                           ~~~~~~^~~~~~~~~~~
horses.cpp:164:18: warning: conversion from 'std::set<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  164 |  int szs = s.size();
      |            ~~~~~~^~
horses.cpp:165:18: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  165 |  int szv = v.size();
      |            ~~~~~~^~
horses.cpp:166:88: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |  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:174:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |  ll bb = stmx.get(v[ind], (ind + 1 == v.size() ? n - 1 : v[ind + 1] - 1));
      |                            ~~~~~~~~^~~~~~~~~~~
horses.cpp:177:77: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |  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:192:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  192 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:199:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  199 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:208:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  208 |  return getans();
      |         ~~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 1 ms 344 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 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Incorrect 0 ms 344 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 582 ms 107700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 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 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Incorrect 0 ms 344 KB Output isn't correct
22 Halted 0 ms 0 KB -