Submission #641876

#	Time	Username	Problem	Language	Result	Execution time	Memory
641876		QwertyPi	말 (IOI15_horses)	C++14	100 / 100	899 ms	64368 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;


ll N;

namespace RMQ{
	ll t[MAXN * 4] = {0};
	void upd(int pos, int val, int v = 0, int tl = 0, int tr = N - 1){
		if(tl == tr){
			t[v] = val;
			return;
		}
		int tm = (tl + tr) / 2;
		if(pos <= tm){
			upd(pos, val, v * 2 + 1, tl, tm);
		}else{
			upd(pos, val, v * 2 + 2, tm + 1, tr);
		}
		t[v] = std::max(t[v * 2 + 1], t[v * 2 + 2]);
	}
	ll max(int l, int r, int v = 0, int tl = 0, int tr = N - 1){
		if(r < tl || tr < l) return 0;
		if(l <= tl && tr <= r) return t[v];
		int tm = (tl + tr) / 2;
		return std::max(max(l, r, v * 2 + 1, tl, tm),
				max(l, r, v * 2 + 2, tm + 1, tr));
	}
};

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 = 0, rans = 1;
	ll c = 1;
	auto ptr = --n1.end();
	while(ptr != n1.begin() && c <= MOD){
		ptr--; c *= x[*ptr];
	}
	c = 1;
	for(; ptr != --n1.end(); ptr++){
		ll v = RMQ::max(*ptr, *next(ptr) - 1);
		if(c * v > ans){
			ans = c * v;
			rans = bit_add.qry(*ptr) > 0 ? 0 : mul(bit_mul.qry(*ptr), v);
		}
		c *= x[*next(ptr)];
	}
	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]);
	}
	
	n1.insert(0); n1.insert(N);
	for(int i = 0; i < N; i++){
		if(x[i] != 1) n1.insert(i);
	}
	
	for(int i = 0; i < N; i++){
		RMQ::upd(i, y[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 && pos != 0) 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;
	RMQ::upd(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: At global scope:
horses.cpp:42:63: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |  void upd(int pos, int val, int v = 0, int tl = 0, int tr = N - 1){
      |                                                             ~~^~~
horses.cpp:55:57: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   55 |  ll max(int l, int r, int v = 0, int tl = 0, int tr = N - 1){
      |                                                       ~~^~~
horses.cpp: In function 'long long int add(long long int, long long int)':
horses.cpp:66:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   66 | 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:66:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   66 | 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:67:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   67 | 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:67:11: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   67 | 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 'long long int query()':
horses.cpp:80:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |   ll v = RMQ::max(*ptr, *next(ptr) - 1);
      |                   ^~~~
horses.cpp:80:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |   ll v = RMQ::max(*ptr, *next(ptr) - 1);
      |                         ~~~~~~~~~~~^~~
horses.cpp:80:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |   ll v = RMQ::max(*ptr, *next(ptr) - 1);
      |                                       ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:90:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   90 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:38:4: note: shadowed declaration is here
   38 | ll N;
      |    ^
horses.cpp:109:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |   RMQ::upd(i, y[i]);
      |               ~~~^
horses.cpp:109:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |   RMQ::upd(i, y[i]);
      |                   ^
horses.cpp:111:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:122:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |  return query();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:127:19: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |  RMQ::upd(pos, val);
      |                   ^
horses.cpp:128:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |  return query();
      |         ~~~~~^~

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