Submission #388012

#	Time	Username	Problem	Language	Result	Execution time	Memory
388012		nafis_shifat	Horses (IOI15_horses)	C++14	54 / 100	1585 ms	29532 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=5e5+5;
const ll inf=1e9;
const ll mod = 1e9 + 7;


ll x[mxn],y[mxn];
int n;
ll bigmod(ll a,ll b) {
	if(b==0)return 1;
	ll mid=b/2;
	ll c=bigmod(a,mid);
	if(b%2==0)return (c*c)%mod;
	c=(c*c)%mod;
	return (a*c)%mod;
}



struct BIT
{
	ll bit[mxn];
	void init() {
		for(int i = 1; i < mxn; i++) bit[i] = 1;
	}	

	void update(int p,ll v) {
		if(p==0) return;
		for(;p<mxn;p+=p&-p) bit[p] = bit[p] * v % mod;
	}
    ll query(int p) {
    	ll r = 1;
    	for(;p>0;p-=p&-p) r = bit[p] * r % mod;
        return r;
    }
} bt;


int calc() {
	int k = 0;

	ll ans = 0;
	ll cm = 0;

	for(int i = n - 1; i >= 0; i--) {
		ll v1 = bt.query(i + 1);
		ll v2 = y[i];
		if(v2 > cm) {
			ans = v1 * v2 % mod;
			cm = x[i] * v2;
		} else {
			cm = cm * x[i];
		}

		if(cm >= inf) break;
	}

	return ans % mod;
}



int init(int N, int X[], int Y[]) {


	for(int i = 0; i < N; i++) {
		x[i] = X[i];
		y[i] = Y[i];
	}

	bt.init();
	n = N;

	
	for(int i = 1; i <= N; i++) {
		bt.update(i,X[i - 1]);
	}
	return calc();
}




int updateX(int pos, int val) {	

	ll tv = bigmod(x[pos],mod - 2);
	bt.update(pos + 1, tv);
	bt.update(pos + 1,val);
	x[pos] = val;
	return calc();
}

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

Compilation message (stderr)

horses.cpp: In function 'int calc()':
horses.cpp:64:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   64 |  return ans % mod;
      |         ~~~~^~~~~
horses.cpp:46:6: warning: unused variable 'k' [-Wunused-variable]
   46 |  int k = 0;
      |      ^

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