제출 #138787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138787		Sorting	말 (IOI15_horses)	C++14	54 / 100	1550 ms	33536 KiB

horses

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int N = 5e5 + 7;
const long long T = 1e9;

int n, *x, *y;
int first;
bool ok = false;

struct Node{
	long long prefix;

	Node(){
		prefix = 1;
	}
};

inline long long Multiply(long long lvalue, long long rvalue){
	return ((lvalue % mod) * (rvalue % mod) % mod); 
}

long long FastPow(long long base, long long exp){
	if(exp == 0){
		return 1ll;
	}

	if(exp & 1){
		return Multiply(base, FastPow(base, exp - 1));
	}

	long long t = FastPow(base, (exp >> 1ll));

	return Multiply(t, t);
}

Node st[4 * N];

void Update(int idx, int l, int r, int sl, int sr, long long mul){
	if(sl > r || sr < l){
		return;
	}
	if(sl <= l && r <= sr){
		st[idx].prefix = Multiply(st[idx].prefix, mul);

		return;
	}

	st[2 * idx].prefix = Multiply(st[idx].prefix, st[2 * idx].prefix);
	st[2 * idx + 1].prefix = Multiply(st[idx].prefix, st[2 * idx + 1].prefix);
	st[idx].prefix = 1;

	int mid = (l + r) >> 1;

	Update(2 * idx, l, mid, sl, sr, mul);
	Update(2 * idx + 1, mid + 1, r, sl, sr, mul);
}

long long Query(int idx, int l, int r, int s){
	if(s < l || s > r){
		return 1;
	}
	if(l == r){
		return st[idx].prefix;
	}

	st[2 * idx].prefix = Multiply(st[idx].prefix, st[2 * idx].prefix);
	st[2 * idx + 1].prefix = Multiply(st[idx].prefix, st[2 * idx + 1].prefix);
	st[idx].prefix = 1;

	int mid = (l + r) >> 1;

	long long ans = 1;
	ans = Multiply(ans, Query(2 * idx, l, mid, s));
	ans = Multiply(ans, Query(2 * idx + 1, mid + 1, r, s));

	return ans;
}

long long init(int _n, int _x[], int _y[]){
	if(!ok){
		n = _n;
		x = _x;
		y = _y;
		ok = true;

		for(int i = 0; i < n; i++){
			Update(1, 0, n - 1, i, n - 1, x[i]);
		}
	}

	long long curr = 1, ans = 0;

	for(int i = n - 1; i >= 0; i--){
		curr *= (long long) x[i];

		first = i;
		if(curr > T){
			break;
		}
	}

	curr = 1;

	for(int i = first; i < n; i++){
		ans = max(ans, (long long)curr * (long long)y[i]);
		if(i != n - 1){
			curr *= (long long)x[i + 1];
		}
	}
	ans %= mod;

	ans = Multiply(ans, Query(1, 0, n - 1, first));

	return ans;
}

long long updateX(int pos, int val){
	Update(1, 0, n - 1, pos, n - 1, Multiply(val, FastPow(x[pos], mod - 2ll)));
	x[pos] = val;

	return init(n, x, y);
}

long long updateY(int pos, int val){
	y[pos] = val;

	return init(n, x, y);
}

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