oj.uz

Submission #787986

# Submission time Handle Problem Language Result Execution time Memory
787986 2023-07-19T15:49:54 Z GusterGoose27 Horses (IOI15_horses) C++17
17 / 100
 181 ms 75836 KB 
#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5+5;
const int inf = 1e9+5;
const int MOD = 1e9+7;

typedef long long ll;

int expo(ll a, int b) {
	ll cur = 1;
	while (b) {
		if (b & 1) {
			cur = (cur*a)%MOD;
		}
		a = (a*a)%MOD;
		b /= 2;
	}
	return cur;
}

int inv(int a) {
	return (a == 1) ? 1 : expo(a, MOD-2);
}

int mx[2*MAXN];
int x[MAXN];
int y[MAXN];
int xinv[MAXN];
int n;

class stree { // range max
public:
	stree() {
		for (int i = n; i < 2*n; i++) mx[i] = y[i-n];
		for (int i = n-1; i > 0; i--) mx[i] = max(mx[2*i], mx[2*i+1]);
	}
	void upd(int p, int v) {
		for (p += n, mx[p] = v; p > 1; p /= 2) {
			mx[p/2] = max(mx[p], mx[p^1]);
		}
	}
	int range_mx(int l, int r) {
		int ans = 0;
		for (l += n, r += n; r > l; r >>= 1, l >>= 1) {
			if (l & 1) ans = max(ans, mx[l++]);
			if (r & 1) ans = max(ans, mx[--r]);
		}
		return ans;
	}
};

stree *tree;
set<int> big;
ll prod = 1;

int solve() {
	ll req = 0; // how big of a value you need to see for it to be worth it
	ll ans = 0;
	ll cur_mult = prod;
	for (auto it = big.rbegin(); it != big.rend() && req < inf; it++) {
		int v = *it;
		int cur_mx = tree->range_mx(v, n);
		if (cur_mx > req) ans = (cur_mult*cur_mx)%MOD;
		req = max(req, (ll)cur_mx);
		req *= x[v];
		cur_mult = (cur_mult*xinv[v])%MOD;
	}
	assert(cur_mult == 1);
	if (mx[1] > req) return mx[1];
	return ans;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++) {
		x[i] = X[i];
		y[i] = Y[i];
		if (x[i] > 1) {
			big.insert(i);
			xinv[i] = inv(x[i]);
		}
		prod = (prod*x[i])%MOD;
	}
	tree = new stree();
	return solve();
}

int updateX(int pos, int val) {	
	prod = (prod*xinv[pos])%MOD;
	big.erase(pos);
	x[pos] = val;
	xinv[pos] = inv(x[pos]);
	prod = (prod*x[pos])%MOD;
	if (x[pos] > 1) big.insert(pos);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	tree->upd(pos, val);
	return solve();
}

Compilation message

horses.cpp: In function 'int expo(ll, int)':
horses.cpp:22:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   22 |  return cur;
      |         ^~~
horses.cpp: In function 'int solve()':
horses.cpp:74:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   74 |  return ans;
      |         ^~~

Subtask #1
17.0 / 17.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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 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 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 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 0 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 340 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 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 340 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 0 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 Runtime error 1 ms 468 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 181 ms 75836 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 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 0 ms 212 KB Output is correct
8 Correct 0 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 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 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 240 KB Output is correct
17 Correct 0 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 0 ms 212 KB Output is correct
21 Runtime error 1 ms 468 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 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 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 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 0 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 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Runtime error 1 ms 468 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -