Submission #167384

#	Time	Username	Problem	Language	Result	Execution time	Memory
167384		kostia244	Horses (IOI15_horses)	C++17	54 / 100	1588 ms	51264 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
const int mod = 1e9 + 7;
const int maxn = 1<<21;
int n, t[maxn], ans = 0;
set<int> chk;
ll mulal = 1;
vi x, ix, y;
void upd(int p, int v) {
	for(t[p += n] = v; p>>=1;)
		t[p] = max(t[p<<1], t[p<<1|1]);
}
int get(int l, int r) {
//	cout << l << " " << r << " " << n << "q\n";
	int ans = 0;
	for(l+=n, r+=n+1; l < r; l>>=1, r>>=1) {
		if(l&1) ans = max(ans, t[l++]);
		if(r&1) ans = max(ans, t[--r]);
	}
//	cout << ans << "q\n";
	return ans;
}
int bp(int a, int p) {
	int r = 1;
	while(p) {
		if(p&1) r = (r*1ll*a)%mod;
		a = (a*1ll*a)%mod;
		p>>=1;
	}
	return r;
}
int calc() {
	auto it = chk.end();
	int p = n-1;
	ll mul = 1, pref = mulal;
	ans = 0;
//	for(auto i : chk) cout << i << " ";
//	cout << "b\n";
	while(mul <= 1000000000 && it-- != chk.begin()) {
		int tmp = get((*it == -1) ? 0 : *it, p);
		if(!ans || tmp > mul) {
			ans = (tmp*1ll*pref)%mod;
			mul = tmp;
		}
//		cout << *it << " " << p << "\n";
//        cout << tmp << " " << pref;
//        cout << " " << mul << "\n";
		if(*it == -1) break;
		pref = (pref*1ll*ix[*it])%mod;
		mul *= x[*it];
		p = *it - 1;
	}
//	cout << ans;
//	cout << "======\n";
	return ans;
}
int init(int N, int X[], int Y[]) {
	n = N;
	ix.resize(n);
	x.resize(n);
	y.resize(n);
	chk.insert(-1);
	for(int i = 0; i < n; i++) {
		x[i] = X[i];
		ix[i] = bp(x[i], mod-2);
		mulal = (mulal*1ll*x[i])%mod;
//		if(x[i] > 1)
			chk.insert(i);
	}
	for(int i = 0; i < n; i++) {
		y[i] = Y[i];
		upd(i, y[i]);
	}
	return calc();
}

int updateX(int pos, int val) {
	if(x[pos] == val) return calc();
//	if(val==1) chk.erase(pos);
//	else if(x[pos]==1) chk.insert(pos);
	x[pos] = val;
	mulal = (mulal*1ll*ix[pos])%mod;
	mulal = (mulal*1ll*x[pos])%mod;
	ix[pos] = bp(x[pos], mod-2);
	return calc();
}

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

Compilation message (stderr)

horses.cpp: In function 'int get(int, int)':
horses.cpp:18:6: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
  int ans = 0;
      ^~~
horses.cpp:8:17: note: shadowed declaration is here
 int n, t[maxn], ans = 0;
                 ^~~
horses.cpp: In function 'int bp(int, int)':
horses.cpp:29:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   if(p&1) r = (r*1ll*a)%mod;
               ~~~~~~~~~^~~~
horses.cpp:30:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   a = (a*1ll*a)%mod;
       ~~~~~~~~~^~~~
horses.cpp: In function 'int calc()':
horses.cpp:45:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    ans = (tmp*1ll*pref)%mod;
          ~~~~~~~~~~~~~~^~~~

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