Submission #868079

#	Time	Username	Problem	Language	Result	Execution time	Memory
868079		waldi	Horses (IOI15_horses)	C++17	100 / 100	167 ms	65040 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define debug(a) cerr << #a << ": " << a << "\n";
#define maxc 1000000000ll
#define ssize(x) (int(x.size()))
#define mod 1000000007ll
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;



struct prz_ilo{
	int N;
	vector<ll> drz;
	void inicjalizuj(vector<ll> vec){
		int n = ssize(vec);
		for(N = 1; N < n;) N <<= 1;
		drz.resize(N<<1, 1ll);
		REP(i, n) drz[N+i] = vec[i];
		for(int i = N; --i;) drz[i] = (drz[i<<1]*drz[i<<1|1])%mod;
	}
	ll wart(int poz){
		return drz[N+poz];
	}
	void ustaw(int poz, ll wart){
		for(poz+=N, drz[poz]=wart; poz>>=1;) drz[poz] = (drz[poz<<1]*drz[poz<<1|1])%mod;
	}
	ll ilo(int p, int k){
		ll ret = 1ll;
		for(p+=N, k+=N+1; p<k; p>>=1, k>>=1){
			if(p&1) ret = (ret*drz[p++])%mod;
			if(k&1) ret = (ret*drz[--k])%mod;
		}
		return ret;
	}
} prz_ilo;// na ciagu x



struct prz_maks{
	int N;
	vector<ll> drz;
	void inicjalizuj(vector<ll> vec){
		int n = ssize(vec);
		for(N = 1; N < n;) N <<= 1;
		drz.resize(N<<1, 0ll);
		REP(i, n) drz[N+i] = vec[i];
		for(int i = N; --i;) drz[i] = max(drz[i<<1], drz[i<<1|1]);
	}
	ll wart(int poz){
		return drz[N+poz];
	}
	void ustaw(int poz, ll wart){
		for(poz+=N, drz[poz]=wart; poz>>=1;) drz[poz] = max(drz[poz<<1], drz[poz<<1|1]);
	}
	ll maks(int p, int k){
		ll ret = 0ll;
		for(p+=N, k+=N+1; p<k; p>>=1, k>>=1){
			if(p&1) ret = max(ret, drz[p++]);
			if(k&1) ret = max(ret, drz[--k]);
		}
		return ret;
	}
} prz_maks;// na ciagu y



int n;
set<int> nie1;// pozycje nie1 w ciagu x, ale pozycja 0 zawsze jest
int wynik(){
	ll wyn = -1ll, musze = -1ll;
	for(auto it = prev(nie1.end()); 1; it = prev(it)){
		if(musze > maxc) break;
		ll maks = prz_maks.maks(*it, n-1);
		if(maks > musze) wyn = (prz_ilo.ilo(0, *it)*maks)%mod, musze = maks;
		musze *= prz_ilo.wart(*it);
		if(it == nie1.begin()) break;
	}
	return wyn;
}



int init(int nn, int xint[], int yint[]){
	n = nn;
	vector<ll> x(n), y(n);
	REP(i, n) x[i] = xint[i], y[i] = yint[i];
	
	/*ll wyn = 0ll;
	REP(i, n){
		ll tmp = y[i];
		FOR(j, 0, i) tmp *= x[j];
		wyn = max(wyn, tmp);
	}
	return wyn;*/
	
	prz_ilo.inicjalizuj(x);
	prz_maks.inicjalizuj(y);
	vector<int> vecnie1;
	REP(i, n) if(!i || x[i] > 1ll) vecnie1.emplace_back(i);
	nie1 = set<int>(all(vecnie1));
	
	return wynik();
}



int updateX(int poz, int wart){	
	prz_ilo.ustaw(poz, wart);
	if(!poz || wart > 1) nie1.emplace(poz);
	else nie1.erase(poz);
	return wynik();
}



int updateY(int poz, int wart){
	prz_maks.ustaw(poz, wart);
	return wynik();
}

Compilation message (stderr)

horses.cpp: In function 'int wynik()':
horses.cpp:82:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   82 |  return wyn;
      |         ^~~

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