oj.uz

Submission #935034

# Submission time Handle Problem Language Result Execution time Memory
935034 2024-02-28T12:43:07 Z PagodePaiva Horses (IOI15_horses) C++17
17 / 100
 54 ms 22352 KB 
#include <bits/stdc++.h>
#include "horses.h"
#define N 500010

using namespace std;

int n;
long long v[N][2];
long long dp[N];
const long long mod = 1e9+7;
long long p = 1;

long long binpow(long long a, long long b, long long m){
	// cout << a << ' ';
	a %= m;
	if(b == 0) return 1;
	long long t = binpow(a, b/2, m);
	if(b % 2 == 0) return (t*t) % m;
	else return ((((t*t) % m)*a) % m);
}

struct Segtree{
	long long tree[4*N];

	long long join(long long a, long long b){
		return (a*b) % mod;
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = v[l][0];
			return;
		}
		int mid = (l+r) >> 1;
		build(2*node,l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	void update(int node, int l, int r, int pos, long long val){
		if(l == r){
			tree[node] = val;
			return;
		}
		int mid = (l+r)/2;
		if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
		else update(2*node, mid+1, r, pos, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	long long query(int node, int l, int r, int tl, int tr){
		if(l <= tl and tr <= r) return tree[node];
		if(l > tr or tl > r) return 1;
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
} seg;

int solve(){
	if(n <= 40){
		dp[0] = 0;
		long long res = 0;
		for(int i = 1;i <= n;i++){
			dp[i] = 0;
			long long int prod = 1;
			for(int j = i;j > 0;j--){
				prod *= v[j][0];
				dp[i] = max(dp[i], dp[j-1] + ((prod-1)*v[i][1]));
				res = max(res, dp[j-1] + prod*v[i][1]);
			}
			// cout << dp[i] << ' ';
		}
		return res % mod;
	}
	long long prod = 1;
	int fim = n;
	for(int i = n-1;i > n-40;i--){
		prod *= v[n+1][0];
		if(prod > 1e9+7) break;
		if(prod*v[fim][1] < v[i][1]){
			fim = i;
			prod = 1;
		}
	}
	return seg.query(1, 1, fim, 1, n);
}

int init(int NN, int X[], int Y[]) {
	n = NN;
	for(int i = 1;i <= n;i++){
		v[i][0] = X[i-1];
		p *= v[i][0];
		p %= mod;
		v[i][1] = Y[i-1];
	}
	seg.build(1, 1, n);
	// cout << n << ' ';
	return solve();
}

int updateX(int pos, int val) {
	v[pos+1][0] = val;
	seg.update(1, 1, n, pos+1,val);
	return solve();
}

int updateY(int pos, int val) {
	v[pos+1][1] = val;
	return solve();
}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:72:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |   return res % mod;
      |          ~~~~^~~~~
horses.cpp:78:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   78 |   if(prod > 1e9+7) break;
      |      ^~~~
horses.cpp:84:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   84 |  return seg.query(1, 1, fim, 1, n);
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 22352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 23.0

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