Submission #798728

#	Time	Username	Problem	Language	Result	Execution time	Memory
798728		Username4132	Horses (IOI15_horses)	C++14	100 / 100	263 ms	52896 KiB

horses

#include "horses.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
#define F first
#define S second


struct node{
	int pr;
	pii mx;
	node(int _pr=0, pii _mx={0, 0}) : pr(_pr), mx(_mx) {}
};

const int MAXN = 500010, MOD = 1000000007;
int n;
node tr[2*MAXN];
set<int> ones;

node combine(node a, node b){
	return node((a.pr*((ll)b.pr))%MOD, max(a.mx, b.mx));
}

void update(int p, node value){
	p+=n;
	tr[p]=value;
	while(p>1) p>>=1, tr[p]=combine(tr[p<<1], tr[p<<1|1]);
}
 
node query(int l, int r){
	node ret = node(1, {0, -1});
	for(l+=n, r+=n; l<r; l>>=1, r>>=1){
		if(l&1) ret = combine(ret, tr[l++]);
		if(r&1) ret = combine(ret, tr[--r]);
	}
	return ret;
} 
 
int solve(){
	ll prod=1;
	vector<int> lis;
	int sz = ones.size();
 
	auto itr = ones.end();
	forn(i, sz){
		itr = prev(itr);
		prod*=tr[n + *itr].pr;
		lis.PB(*itr);
		if(prod>1000000010) break;
	}
	reverse(lis.begin(), lis.end());
 
	pli basic = query(0, n).mx;
	if(lis.empty()) return basic.F;

	ll p=1;
	pli mx={-1, -1};
	for(int el:lis){
		if(el!=lis.front()) p*=tr[n + el].pr;
		pli opt = query(el, n).mx;
		opt.F*=p;
		mx = max(mx, opt);
	}
	if(mx.F > (basic.F / tr[n + lis.front()].pr)) return (tr[n+mx.S].mx.F*((ll)query(0, mx.S + 1).pr))%MOD;
	else return basic.F;
}
 
int init(int N, int X[], int Y[]) {
	n=N;
	forn(i, n){
		tr[n+i]=node(X[i], {Y[i], i});
		if(tr[n+i].pr!=1) ones.insert(i);
	}
	dforsn(i, 1, n) tr[i]=combine(tr[i<<1], tr[i<<1|1]);
	return solve();
}
 
int updateX(int pos, int val) {	
	if(tr[n+pos].pr==1 && val!=1) ones.insert(pos);
	if(tr[n+pos].pr!=1 && val==1) ones.erase(pos);
	update(pos, node(val, tr[n+pos].mx));
	return solve();
}
 
int updateY(int pos, int val) {
	update(pos, node(tr[n+pos].pr, {val, pos}));
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'node combine(node, node)':
horses.cpp:31:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   31 |  return node((a.pr*((ll)b.pr))%MOD, max(a.mx, b.mx));
      |              ~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int solve()':
horses.cpp:52:20: warning: conversion from 'std::set<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   52 |  int sz = ones.size();
      |           ~~~~~~~~~^~
horses.cpp:15:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 | #define F first
      |           ^
horses.cpp:64:31: note: in expansion of macro 'F'
   64 |  if(lis.empty()) return basic.F;
      |                               ^
horses.cpp:74:100: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   74 |  if(mx.F > (basic.F / tr[n + lis.front()].pr)) return (tr[n+mx.S].mx.F*((ll)query(0, mx.S + 1).pr))%MOD;
      |                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:15:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 | #define F first
      |           ^
horses.cpp:75:20: note: in expansion of macro 'F'
   75 |  else return basic.F;
      |                    ^

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