oj.uz

Submission #567843

# Submission time Handle Problem Language Result Execution time Memory
567843 2022-05-24T09:15:01 Z ngpin04 Horses (IOI15_horses) C++17
17 / 100
 14 ms 10760 KB 
#include <bits/stdc++.h>
#include "horses.h"
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct segtree {
	int n;
	vector <int> st;

	segtree(int _n = 0){
		n = _n;
		st.assign((n << 2) + 5, 0);
	}

	void update(int id, int l, int r, int pos, int val) {
		if (l > pos || r < pos)
			return;
		if (l == r) {
			st[id] = val;
			return;
		}
		int mid = (l + r) >> 1;
		update(id << 1, l, mid, pos, val);
		update(id << 1 | 1, mid + 1, r, pos, val);
		st[id] = max(st[id << 1], st[id << 1 | 1]);
	}

	void update(int pos, int val) {
		update(1, 1, n, pos, val);
	}

	int getmax(int id, int l, int r, int u, int v) {
		if (l > v || r < u)
			return 0;
		if (l >= u && r <= v) 
			return st[id];
		int mid = (l + r) >> 1;
		int lnode = getmax(id << 1, l, mid, u, v);
		int rnode = getmax(id << 1 | 1, mid + 1, r, u, v);
		return max(lnode, rnode);
	}

	int getmax(int l, int r) {
		return getmax(1, 1, n, l, r);
	}
};

struct BIT {
	int n;
	vector <int> bit;

	BIT(int _n = 0){
		n = _n;
		bit.assign(n + 5, 1);
	}

	void update(int pos, int val) {
		for (; pos <= n; pos += pos & -pos)
			bit[pos] = (long long) bit[pos] * val % mod;
	}

	int getmul(int pos) {
		int res = 1;
		for (; pos; pos -= pos & -pos)
			res = (long long) res * bit[pos] % mod;
		return res;
	}
};


BIT bit;
segtree st; 

set <int> pos;

int l[N];
int r[N];
int x[N];
int y[N];
int n;

int bpow(int x, int k) {
	int res = 1;
	for (; k; k >>= 1, x = (long long) x * x % mod)
		if (k & 1) 
			res = (long long) res * x % mod;
	return res;
}

void build() {
	st = segtree(n);
	bit = BIT(n);
	pos.insert(0);
	pos.insert(n + 1);
	r[0] = n + 1;
	l[n + 1] = 0;

	for (int i = 1; i <= n; i++) if (x[i] > 1) {
		auto it = pos.upper_bound(i);
		int v = *it;
		int u = *(--it);
		l[i] = u;
		r[i] = v;

		r[u] = i;
		l[v] = i;
		
		pos.insert(i);
		bit.update(i, x[i]);
	}

	for (int i = 1; i <= n; i++)
		st.update(i, y[i]);
}

int solve() {
	vector <int> cand;
	long long tot = 1;
	for (int i = n + 1; i > 0 && tot < oo; i = l[i]) {
		cand.push_back(i);
		if (i <= n)
			tot *= x[i];
	}

	if (tot < oo && cand.back() != 1)
		cand.push_back(1);

	reverse(ALL(cand));
	long long ans = 0;
	long long cur = 1;
	int pos = -1;
	for (int it = 0; it + 1 < (int) cand.size(); it++) {
		int i = cand[it];
		int j = cand[it + 1];
		cur *= x[i];

		if (st.getmax(i, j - 1) > ans / cur) {
			pos = it;
			ans = cur * st.getmax(i, j - 1);
		}
	}	
	int ret = bit.getmul(cand[pos]);
	ret = (long long) ret * st.getmax(cand[pos], cand[pos + 1] - 1);
	return ret;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 1; i <= n; i++)
		x[i] = X[i - 1];

	for (int i = 1; i <= n; i++)
		y[i] = Y[i - 1];

	build();
	return solve();
}

int updateX(int i, int val) {	
	i++;
	if (x[i] > 1) {
		pos.erase(i);
		auto it = pos.upper_bound(i);
		int v = *it;
		int u = *(--it);

		r[u] = v;
		l[v] = u;
	}

	bit.update(i, bpow(x[i], mod - 2));

	x[i] = val;

	bit.update(i, x[i]);

	if (x[i] > 1) {
		auto it = pos.upper_bound(i);
		int v = *it;
		int u = *(--it);

		r[u] = i;
		l[v] = i;

		r[i] = v;
		l[i] = u;

		pos.insert(i);
	}
	return solve();
}

int updateY(int pos, int val) {
	pos++;
	st.update(pos, val);
	return solve();
}

//#include "grader.cpp"

Compilation message

horses.cpp: In function 'int rand(int, int)':
horses.cpp:20:11: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   20 |  return l + rd() % (r - l + 1);
      |         ~~^~~~~~~~~~~~~~~~~~~~
horses.cpp: In member function 'void BIT::update(int, int)':
horses.cpp:81:42: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   81 |    bit[pos] = (long long) bit[pos] * val % mod;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int BIT::getmul(int)':
horses.cpp:87:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   87 |    res = (long long) res * bit[pos] % mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int bpow(int, int)':
horses.cpp:104:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  104 | int bpow(int x, int k) {
      |          ~~~~^
horses.cpp:100:5: note: shadowed declaration is here
  100 | int x[N];
      |     ^
horses.cpp:106:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  106 |  for (; k; k >>= 1, x = (long long) x * x % mod)
      |                         ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:108:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  108 |    res = (long long) res * x % mod;
      |          ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int solve()':
horses.cpp:153:6: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  153 |  int pos = -1;
      |      ^~~
horses.cpp:96:11: note: shadowed declaration is here
   96 | set <int> pos;
      |           ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:169:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  169 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:22:11: note: shadowed declaration is here
   22 | const int N = 1e5 + 5;
      |           ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:215:17: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
  215 | int updateY(int pos, int val) {
      |             ~~~~^~~
horses.cpp:96:11: note: shadowed declaration is here
   96 | set <int> pos;
      |           ^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 0 ms 212 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 14 ms 10760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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