Submission #876063

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
876063	2023-11-21T07:52:50 Z	Elvin_Fritl	Horses (IOI15_horses)	C++17	Compilation error	0 ms	0 KB

horses

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

typedef long long ll;

const int N = 3e5 + 545 , inf = 1e9 + 199 , mod = 1e9 + 7;

    #include "horses.h"

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

segtree S;


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


ll 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{
		s.erase(s.find(pos));
	}
	return calc();
}
 
int updateY(int pos, int val) {
	S.update(1, 0, n-1, pos, val);
	return calc();
}

Compilation message

horses.cpp: In function 'll bp(ll, ll)':
horses.cpp:43:10: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   43 | ll bp(ll n,ll m){
      |       ~~~^
horses.cpp:39:4: note: shadowed declaration is here
   39 | ll n , x[N] , y[N];
      |    ^
horses.cpp: In function 'll calc()':
horses.cpp:75:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   75 |   int i = *it;
      |           ^~~
horses.cpp:76:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |   int j = *(++it);
      |           ^~~~~~~
horses.cpp:80:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   80 |   mx = max(mx, res * S.get(1, 0, n-1, i, j-1));
      |                                  ~^~
horses.cpp: At global scope:
horses.cpp:88:4: error: ambiguating new declaration of 'll init(int, int*, int*)'
   88 | ll init(int nn, int X[], int Y[]) {
      |    ^~~~
In file included from horses.cpp:8:
horses.h:4:5: note: old declaration 'int init(int, int*, int*)'
    4 | int init(int N, int X[], int Y[]);
      |     ^~~~
horses.cpp: In function 'll init(int, int*, int*)':
horses.cpp:95:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   95 |   S.update(1, 0, n - 1, i, y[i]);
      |                  ~~^~~
horses.cpp:99:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   99 |  for(int i=n-1;i>=0;i--) {
      |            ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:119:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:123:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  123 |  S.update(1, 0, n-1, pos, val);
      |                 ~^~
horses.cpp:124:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  124 |  return calc();
      |         ~~~~^~