Submission #876081

#	Time	Username	Problem	Language	Result	Execution time	Memory
876081		Elvin_Fritl	Horses (IOI15_horses)	C++17	37 / 100	421 ms	55024 KiB

horses

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

typedef long long ll;

const int N = 5e5 + 545 , inf = 1e9 + 12 , mod = 1e9 + 7;

    #include "horses.h"

 
struct segtree {
	int tree[N*4];
	void update(int v,int l,int r,int pos,int val) {
		if(l == r) {
			tree[v] = val; 
			return;
		}
		int mid = (l+r)/2;
		if(pos <= mid) {
			update((v*2), l, mid, pos, val);
		}
		else {
			update((v*2 + 1), mid + 1, r, pos, val);
		}
		tree[v] = max(tree[(v*2)], tree[(v*2 + 1)]);
	}
	int get(int v,int l,int r,int ml,int mr) {
		if(mr < l || r < ml || l > r){
			return 0LL;
		}
		if(ml <= l && r <= mr){
			return tree[v];
		}
		int mid = (l+r)/2;
		return max(get((v*2), l, mid, ml, mr), get((v*2 + 1), mid + 1, r, ml, mr));
	}
	
};
int n;
ll x[N] , y[N];
set<int> s;
ll tmp = 1;
 
ll bp(ll x,ll m){
    if(m == 0){
        return 1LL;
    }
    if(m == 1){
        return x%mod;
    }
    if(m%2==0){
        return bp(x*x%mod,m/2)%mod;
    }
    return x*bp(x,m-1)%mod;
}

segtree S;


int calc() {
	ll res = 1 , ind = -1;
	assert((int)s.size() >= 2);
	auto it = next(s.rbegin());
	while(it != s.rend()) {
		res *= x[*it];
		ind = *it;
		if(res > inf){
			break;
		}
		it = next(it);
	}
	auto it2 = s.lower_bound(ind);
	ll mx = 0; 
	res = 1;
	while(next(it2) != s.end()) {
		int i = *it2;
		int j = *(next(it2));
		if(i != ind){
			res = res*x[i];
		}
		ll ans = S.get(1, 0, n-1, i, j-1);
		mx = max(mx, res*ans);
		it2 = next(it2);
	}
	mx %= mod;
	return tmp*bp(res,mod-2)%mod*mx%mod;
}


int init(int nn, int X[], int Y[]) {
	n = nn;
	for(int i=0;i<n;i++) {
		x[i] = X[i];
		y[i] = Y[i];
	}
	for(int i=0;i<n;i++) {
		S.update(1, 0, n - 1, i, y[i]);
	}
	s.insert(0);
	s.insert(n);
	for(int i=n-1;i>=0;i--) {
		if(x[i] > 1) {
			tmp = (tmp * x[i])%mod;
			s.insert(i); 
		}
	}
	return calc();
}
 
 
int updateX(int pos, int val) {
	tmp = (tmp * bp(x[pos], mod-2))%mod;
	x[pos] = val;
	tmp = (tmp*val)%mod;
	if(val > 1 || pos == 0){
		s.insert(pos);
	}
	else{
		assert(s.find(pos) != s.end());
		s.erase(pos);
	}
	return calc();
}
 
int updateY(int pos, int val) {
	S.update(1, 0, n-1, pos, val);
	return calc();
}

Compilation message (stderr)

horses.cpp: In function 'll bp(ll, ll)':
horses.cpp:44:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   44 | ll bp(ll x,ll m){
      |       ~~~^
horses.cpp:40:4: note: shadowed declaration is here
   40 | ll x[N] , y[N];
      |    ^
horses.cpp: In function 'int calc()':
horses.cpp:72:27: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::key_type' {aka 'int'} may change value [-Wconversion]
   72 |  auto it2 = s.lower_bound(ind);
      |                           ^~~
horses.cpp:86:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   86 |  return tmp*bp(res,mod-2)%mod*mx%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   97 |   S.update(1, 0, n - 1, i, y[i]);
      |                            ~~~^

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