제출 #1326449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326449		farica	Horses (IOI15_horses)	C++20	20 / 100	438 ms	32656 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define se second
#define fi first

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int MOD = 1e9 + 7;
const ll MAX = 1e9 + 1;

vi x, y;
int n;

struct Node {
	int p, p2, st;
};

vector<Node>segm;

void buildP(int pos, int l, int r) {
	if(l == r) {
		segm[pos].p = segm[pos].p2 = x[l];
		return;
	}
	int m = (l+r)/2;
	buildP(2*pos+1, l, m);
	buildP(2*pos+2, m+1, r);
	segm[pos].p = (1ll * segm[2*pos+1].p * segm[2*pos+2].p) % MOD;
	segm[pos].p2 = min(MAX, 1ll * segm[2*pos+1].p2 * segm[2*pos+2].p2);
}
	
void updateP(int pos, int l, int r, int ind) {
	if(l == r) {
		segm[pos].p = segm[pos].p2 = x[ind];
		return;
	}
	int m = (l+r)/2;
	if(ind <= m) updateP(2*pos+1, l, m, ind);
	else updateP(2*pos+2, m+1, r, ind);
	segm[pos].p = (1ll * segm[2*pos+1].p * segm[2*pos+2].p) % MOD;
	segm[pos].p2 = min(MAX, 1ll * segm[2*pos+1].p2 * segm[2*pos+2].p2);
}

int queryP(int pos, int l, int r, int ql, int qr, bool type) {
	if(l > qr or r < ql) return 1;
	if(l >= ql && r <= qr) return (type ? segm[pos].p2 : segm[pos].p);
	int m = (l+r)/2;
	ll tmp = 1ll * queryP(2*pos+1, l, m, ql, qr, type) * queryP(2*pos+2, m+1, r, ql, qr, type);
	if(type) return min(MAX, tmp);
	else return (tmp % MOD);
}

void build(int pos, int l, int r) {
	if(l == r) {
		segm[pos].st = l;
		return;
	}
	int m = (l+r)/2;
	build(2*pos+1, l, m);
	build(2*pos+2, m+1, r);
	int L = segm[2*pos+1].st, R = segm[2*pos+2].st;
	if(queryP(1, 0, n-1, L+1, R, true) >= (int)ceil(y[L]/(double)y[R])) segm[pos].st = R;
	else segm[pos].st = L;
}

void update(int pos, int l, int r, int ind) {
	if(l == r) return;
	int m = (l+r)/2;
	if(ind <= m) update(2*pos+1, l, m, ind);
	else update(2*pos+2, m+1, r, ind);
	int L = segm[2*pos+1].st, R = segm[2*pos+2].st;
	if(queryP(1, 0, n-1, L+1, R, true) >= (int)ceil(y[L]/(double)y[R])) segm[pos].st = R;
	else segm[pos].st = L;
}

int calc() {
	int ind = segm[1].st;
	return (1ll * queryP(1, 0, n-1, 0, ind, false) * y[ind]) % MOD;
}
	
int init(int N, int X[], int Y[]) {
	x.resize(N);
	y.resize(N);
	n = N;
	segm.resize(4*N);
	for(int i=0; i<N; ++i) {
		x[i] = X[i];
		y[i] = Y[i];
	}
	buildP(1, 0, n-1);
	build(1, 0, n-1);
	return calc();
}

int updateX(int pos, int val) {	
	x[pos] = val;
	updateP(1, 0, n-1, pos);
	update(1, 0, n-1, pos);
	return calc();
}

int updateY(int pos, int val) {
	y[pos] = val;
	update(1, 0, n-1, pos);
	return calc();
}

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