Submission #574108

#	Time	Username	Problem	Language	Result	Execution time	Memory
574108		perchuts	Horses (IOI15_horses)	C++17	100 / 100	206 ms	74860 KiB

horses

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const ll inf = 1e9+1ll;
const int mod = 1e9+7;
const int maxn = 5e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

// #include "horses.h"
// construir uma seg com merge: preciso do melhor segmento,
// produtorio do melhor segmento, sufixo dos x's depois do melhor segmento, produtorio de todos os x's do segmento
// merge: ou continuo com o da esquerda, ou continuo com o da direita, ou vou da esquerda pra direita
// (mantenho o y da direita)
// a resposta é automaticamente dada por seg[1].
// cuidado: os valores facilmente passarao de 1e18, entao como estamos comparando apenas com o y (que vai ate 1e9)
// , se o valor passa de 1e9 nao faco update dele mais (apenas pra comparacao, na resposta tem que tirar o mod)

ll x[maxn], y[maxn];
int n;

struct node{
	ll best,bestmod, suf, tot, totmod;
	int idx;
}seg[4*maxn];

node merge(node l,node r){
	node res;

	res.tot = min(inf, l.tot*r.tot), res.totmod = (l.totmod*r.totmod)%mod;

	if(y[l.idx]>l.suf*r.best)res.best = l.best, res.bestmod = l.bestmod,
	res.suf = min(inf, l.suf*r.tot), res.idx = l.idx;

	else res.best = min(l.tot*r.best,inf), res.bestmod = (l.totmod*r.bestmod)%mod,
	res.suf = r.suf, res.idx = r.idx;

	return res;
}

void build(int i,int l,int r){
	if(l==r){
		seg[i].best = min(inf,x[l]*y[l]), seg[i].bestmod = (x[l]*y[l])%mod, seg[i].suf = 1ll,
		seg[i].tot = seg[i].totmod = x[l], seg[i].idx = l;
		return; 
	}
	int md = (l+r)/2;
	build(2*i,l,md), build(2*i+1,md+1,r);
	seg[i] = merge(seg[2*i],seg[2*i+1]);
}

void update(int i,int l,int r,int ind,bool mode,ll d){
	if(l>ind||r<ind)return;
	if(l==r){
		if(mode)x[l] = d;
		else y[l] = d;
		seg[i].best = min(inf,x[l]*y[l]), seg[i].bestmod = (x[l]*y[l])%mod, seg[i].suf = 1ll,
		seg[i].tot = seg[i].totmod = x[l], seg[i].idx = l;
		return; 
		return;
	}
	int md = (l+r)/2;
	update(2*i,l,md,ind,mode,d), update(2*i+1,md+1,r,ind,mode,d);
	seg[i] = merge(seg[2*i],seg[2*i+1]);
}

int init(int N, int X[], int Y[]) {
	n = N;
	for(int i=1;i<=n;++i)x[i] = ll(X[i-1]), y[i] = ll(Y[i-1]);
	build(1,1,n);
	return int(seg[1].bestmod);
}

int updateX(int pos, int val) {	
	update(1,1,n,pos+1,1,ll(val));
	return int(seg[1].bestmod);
}

int updateY(int pos, int val) {
	update(1,1,n,pos+1,0,ll(val));
	return int(seg[1].bestmod);
}


// static char _buffer[1024];
// static int _currentChar = 0;
// static int _charsNumber = 0;
// static FILE *_inputFile, *_outputFile;

// static inline int _read() {
//     if (_charsNumber < 0) {
//         exit(1);
//     }
//     if (!_charsNumber || _currentChar == _charsNumber) {
//         _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
//         _currentChar = 0;
//     }
//     if (_charsNumber <= 0) {
//         return -1;
//     }
//     return _buffer[_currentChar++];
// }

// static inline int _readInt() {
//     int c, x, s;
//     c = _read();
//     while (c <= 32) c = _read();
//     x = 0;
//     s = 1;
//     if (c == '-') {
//         s = -1;
//         c = _read();
//     }
//     while (c > 32) {
//         x *= 10;
//         x += c - '0';
//         c = _read();
//     }
//     if (s < 0) x = -x;
//     return x;
// }


// int main() {
	
// 	int N;cin>>N;

// 	int *X = (int*)malloc(sizeof(int)*(unsigned int)N);
// 	int *Y = (int*)malloc(sizeof(int)*(unsigned int)N);

// 	for (int i = 0; i < N; i++) {
// 		cin>>X[i];
// 	}

// 	for (int i = 0; i < N; i++) {
// 		cin>>Y[i];
// 	}	

// 	cout<<init(N,X,Y)<<endl;
//  	int M;cin>>M;

// 	for (int i = 0; i < M; i++) {
// 		int type,pos,val;cin>>type>>pos>>val;
// 		if (type == 1) {
// 			cout<<updateX(pos,val)<<endl;
// 		} else if (type == 2) {
// 			cout<<updateY(pos,val)<<endl;
// 		}
// 	}
// 	return 0;
// }

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