Submission #641862

#	Time	Username	Problem	Language	Result	Execution time	Memory
641862		QwertyPi	Horses (IOI15_horses)	C++14	54 / 100	1568 ms	56896 KiB

horses

#include "horses.h"


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

const ll MOD = 1e9 + 7;

const ll MAXN = 5e5 + 11;

ll x[MAXN], y[MAXN];

struct BIT{
	ll bit[MAXN] = {0}, id;
	void init(ll id, ll (*f)(ll, ll)) { 
		this->id = id; 
		fill(bit, bit + MAXN, id);
		combine = f;
	}
	void add(ll pos, ll val){
		pos++;
		for(ll i = pos; i < MAXN; i += i & -i){
			bit[i] = combine(bit[i], val);
		}
	}
	ll qry(ll pos){
		pos++; ll ret = id;
		for(ll i = pos; i; i -= i & -i){
			ret = combine(ret, bit[i]);
		}
		return ret;
	}
	ll (*combine)(ll, ll);
} bit_add, bit_mul;

struct RMQ{
	
};

ll N;
set<ll> n1;


ll add(ll x, ll y) { return x + y; }
ll mul(ll x, ll y) { return x * y % MOD; }
ll bp(ll a, ll b) { if(b == 0) return 1; return bp(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD; }
ll mi(ll a) { return bp(a, MOD - 2); }

ll query() {
	ll ans = 1, rans = 1;
	ll c = 1;
	ll i;
	for(i = N - 1; i >= 0; i--){
		if(i == -1) break;
		c *= x[i];
		if(c > MOD) break;
	}
	c = 1;
	for(; i < N; i++){
		if(c * y[i] > ans){
			ans = c * y[i];
			rans = bit_add.qry(i) > 0 ? 0 : mul(bit_mul.qry(i), y[i]);
		}
		c *= x[i + 1];
	}
	return rans;
}

int init(int N, int X[], int Y[]) {
	::N = N;
	bit_add.init(0, add);
	bit_mul.init(1, mul);
	
	for(int i = 0; i < N; i++) x[i] = X[i];
	for(int i = 0; i < N; i++) y[i] = Y[i];

	for(int i = 0; i < N; i++){
		if(x[i] == MOD) bit_add.add(i, 1);
		else bit_mul.add(i, x[i]);
	}

	for(int i = 0; i < N; i++){
		if(x[i] != 1) n1.insert(i);
	}
	return query();
}

int updateX(int pos, int val) {	
	if(x[pos] == MOD) bit_add.add(pos, -1);
	else bit_mul.add(pos, mi(x[pos]));
	if(x[pos] != 1) n1.erase(pos);
	x[pos] = val;
	if(x[pos] == MOD) bit_add.add(pos, 1);
	else bit_mul.add(pos, x[pos]);
	if(x[pos] != 1) n1.insert(pos);
	return query();
}

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

Compilation message (stderr)

horses.cpp: In member function 'void BIT::init(long long int, long long int (*)(long long int, long long int))':
horses.cpp:16:15: warning: declaration of 'id' shadows a member of 'BIT' [-Wshadow]
   16 |  void init(ll id, ll (*f)(ll, ll)) {
      |               ^
horses.cpp:15:22: note: shadowed declaration is here
   15 |  ll bit[MAXN] = {0}, id;
      |                      ^~
horses.cpp: In function 'long long int add(long long int, long long int)':
horses.cpp:45:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   45 | ll add(ll x, ll y) { return x + y; }
      |                 ^
horses.cpp:12:13: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |             ^
horses.cpp:45:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   45 | ll add(ll x, ll y) { return x + y; }
      |           ^
horses.cpp:12:4: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |    ^
horses.cpp: In function 'long long int mul(long long int, long long int)':
horses.cpp:46:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   46 | ll mul(ll x, ll y) { return x * y % MOD; }
      |                 ^
horses.cpp:12:13: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |             ^
horses.cpp:46:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   46 | ll mul(ll x, ll y) { return x * y % MOD; }
      |           ^
horses.cpp:12:4: note: shadowed declaration is here
   12 | ll x[MAXN], y[MAXN];
      |    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:70:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   70 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:41:4: note: shadowed declaration is here
   41 | ll N;
      |    ^
horses.cpp:86:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:97:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:102:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |  return query();
      |         ~~~~~^~

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