Submission #221807

#	Time	Username	Problem	Language	Result	Execution time	Memory
221807		patrikpavic2	Horses (IOI15_horses)	C++17	100 / 100	1020 ms	88312 KiB

horses

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  horses
* score: 100.0
* date:  2019-06-23 09:59:51.864112
*/
#include "horses.h"
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <vector>

#define PB push_back

using namespace std;

typedef __int128 ll;
typedef pair < int, int > pii;
typedef vector < int > vi;

const int OFF = (1 << 19);
const ll MOD = 1e9 + 7;
const int N = 1e6 + 500;

ll mul[2 * OFF];
ll mx[2 * OFF], n, X[N], Y[N];
set < int > s;
vi v;

ll query_mul(int i,int a,int b,int lo,int hi){
	if(lo <= a && b <= hi) return mul[i];
	if(a > hi || b < lo) return 1;
	return query_mul(2 * i, a, (a + b) / 2, lo, hi) * query_mul(2 * i + 1, (a + b) / 2 + 1, b, lo, hi) % MOD;
}

ll query_mx(int i,int a,int b,int lo,int hi){
	if(lo <= a && b <= hi) return mx[i];
	if(a > hi || b < lo) return 1;
	return max(query_mx(2 * i, a, (a + b) / 2, lo, hi), query_mx(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}

void update_mul(int i,ll X){
	if(mul[OFF + i] > 1) s.erase(i);
	if(X > 1)            s.insert(i);
	mul[OFF + i] = X;
	for(i = (i + OFF) / 2; i ; i /= 2)
		mul[i] = mul[2 * i] * mul[2 * i + 1] % MOD;
}

void update_mx(int i, ll Y){
	mx[OFF + i] = Y;
	for(i = (i + OFF) / 2; i ; i /= 2)
		mx[i] = max(mx[2 * i], mx[2 * i + 1]);
}

ll solve(){
	ll cur = 1, sol = 1;
	vi v;
	auto it = s.rbegin();
	v.PB(n); 
	//printf("s %d\n", s.size());
	for(; v.size() <= s.size() && cur < MOD;){
		v.PB(*it); cur *= X[*it]; it++;
		if(cur >= (ll)MOD) break;
	}
	reverse(v.begin(), v.end());
	cur = 1;
	for(int i = 0;i + 1 < v.size();i++){
		cur *= (ll)X[v[i]];
		//printf("cur %lld mx %lld\n", cur, query_mx(1, 0, OFF - 1,v[i], v[i + 1] - 1));
		sol = max(sol, cur * query_mx(1, 0, OFF - 1,v[i], v[i + 1] - 1));
	}
	//printf("gotov\n");
	if(v.size() > s.size()) return max(sol, (ll)mx[1]) % MOD;
	return sol % (ll)MOD * query_mul(1, 0, OFF - 1, 0, v[0] - 1) % MOD;
}


int init(int N, int XX[], int YY[]) {
	for(int i = 0;i < N;i++) X[i] = XX[i], Y[i] = YY[i];
	n = N;
	for(int i = 0;i < n;i++)
		update_mul(i, X[i]), update_mx(i, Y[i]);
	return solve();
}

int updateX(int pos, int val) {	
	update_mul(pos, val); X[pos] = val;
	return solve();
}

int updateY(int pos, int val) {
	update_mx(pos, val); Y[pos] = val;
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'void update_mul(int, ll)':
horses.cpp:46:27: warning: declaration of 'X' shadows a global declaration [-Wshadow]
 void update_mul(int i,ll X){
                           ^
horses.cpp:30:20: note: shadowed declaration is here
 ll mx[2 * OFF], n, X[N], Y[N];
                    ^
horses.cpp: In function 'void update_mx(int, ll)':
horses.cpp:54:27: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
 void update_mx(int i, ll Y){
                           ^
horses.cpp:30:26: note: shadowed declaration is here
 ll mx[2 * OFF], n, X[N], Y[N];
                          ^
horses.cpp: In function 'll solve()':
horses.cpp:62:5: warning: declaration of 'v' shadows a global declaration [-Wshadow]
  vi v;
     ^
horses.cpp:32:4: note: shadowed declaration is here
 vi v;
    ^
horses.cpp:64:8: warning: conversion to 'std::vector<int>::value_type {aka int}' from 'll {aka __int128}' may alter its value [-Wconversion]
  v.PB(n); 
        ^
horses.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i + 1 < v.size();i++){
                ~~~~~~^~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:83:35: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int XX[], int YY[]) {
                                   ^
horses.cpp:27:11: note: shadowed declaration is here
 const int N = 1e6 + 500;
           ^
horses.cpp:88:14: warning: conversion to 'int' from 'll {aka __int128}' may alter its value [-Wconversion]
  return solve();
         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:93:14: warning: conversion to 'int' from 'll {aka __int128}' may alter its value [-Wconversion]
  return solve();
         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:98:14: warning: conversion to 'int' from 'll {aka __int128}' may alter its value [-Wconversion]
  return solve();
         ~~~~~^~

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