Submission #743757

#	Time	Username	Problem	Language	Result	Execution time	Memory
743757		Abrar_Al_Samit	말 (IOI15_horses)	C++17	37 / 100	449 ms	29476 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;

const int nax = 5e5 + 2;
const int mod = 1e9 + 7;
const int MX = 1e9;
long long x[nax], y[nax];
long long preprod[nax];
int n;

long long mul(long long a, long long b) {
	return (a * b) % mod;
}
long long quickpow(long long a, long long b) {
	long long ret = 1;
	while(b) {
		if(b&1) ret = mul(ret, a);
		a = mul(a, a);
		b >>= 1;
	}
	return ret;
}
int get() {
	for(int i=max(0, n-30); i<n; ++i) {
		long long cur = preprod[i];

		long long cnt = 1;
		bool ok = false;
		for(int j=i+1; j<n; ++j) {
			cnt *= x[j];
			if(cnt * y[j] > y[i]) {
				ok = true;
				break;
			}
			if(cnt>MX) {
				ok = true;
				break;
			}
		}
		if(!ok) {
			return (cur * y[i]) % mod;
		}
	}
}
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];
		preprod[i] = x[i];
		if(i) preprod[i] = mul(preprod[i], preprod[i-1]);
	}
	return get();
}

int updateX(int pos, int val) {	
	for(int i=max(pos, n-30); i<n; ++i) {
		preprod[i] = mul(preprod[i], quickpow(x[pos], mod-2));
		preprod[i] = mul(preprod[i], val);
	}
	x[pos] = val;
	return get();
}

int updateY(int pos, int val) {
	y[pos] = val;
	return get();
}

Compilation message (stderr)

horses.cpp: In function 'int get()':
horses.cpp:42:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |    return (cur * y[i]) % mod;
      |           ~~~~~~~~~~~~~^~~~~
horses.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23