Submission #1149838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149838		mychecksedad	Horses (IOI15_horses)	C++20	100 / 100	928 ms	46064 KiB

horses

/* Author : Mychecksdead  */
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 3e6+100, M = 1e5+10, K = 52, MX = 30;
ll INF = MOD;
ll x[N], y[N], S[N], V[N];
array<ll, 2> T[N];
int n;
ll get2(int l, int r, int ql, int qr, int k){
	if(ql > r || l > qr) return 1ll;
	if(ql <= l && r <= qr) return V[k];
	int m = l+r>>1;
	return get2(l, m, ql, qr, k<<1) * get2(m+1, r, ql, qr, k<<1|1) % MOD;
}
ll get(int l, int r, int ql, int qr, int k){
	if(ql > r || l > qr) return 1ll;
	if(ql <= l && r <= qr) return S[k];
	int m = l+r>>1;
	return min(INF, get(l, m, ql, qr, k<<1) * get(m+1, r, ql, qr, k<<1|1));
}
array<ll, 2> comb(array<ll, 2> a, array<ll, 2> b){
	ll f = get(0, n - 1, a[0] + 1, b[0], 1);
	if(f * b[1] > a[1]) return b;
	return a; 
}
void UPD(int l, int r, int ql, int qr, int k){
	if(ql > r || l > qr) return;
	if(ql <= l && r <= qr){
		if(l==r) return;
		T[k] = comb(T[k<<1], T[k<<1|1]);
	}else{
		int m = l+r>>1;
		UPD(l, m, ql, qr, k<<1);
		UPD(m+1, r, ql, qr, k<<1|1);
		T[k] = comb(T[k<<1], T[k<<1|1]);
	}
}
void upd(int l, int r, int pos, int k, ll val){
	if(l==r){
		x[l]=val;
		S[k]=x[l];
		V[k]=x[l];
	}else{
		int m= l+r>>1;
		if(pos<=m) upd(l,  m, pos,k<<1, val);
		else upd(m+1, r, pos, k<<1|1, val);
		T[k] = comb(T[k<<1], T[k<<1|1]);
		S[k] = min(S[k<<1] * S[k<<1|1], INF);
		V[k] = V[k<<1] * V[k<<1|1] % MOD;
	}
}
void upd2(int l, int r, int pos, int k, ll val){
	if(l==r){
		y[l]=val;
		T[k]={l, y[l]};
	}else{
		int m= l+r>>1;
		if(pos<=m) upd2(l,  m, pos,k<<1, val);
		else upd2(m+1, r, pos, k<<1|1, val);
		T[k] = comb(T[k<<1], T[k<<1|1]);
		S[k] = min(S[k<<1] * S[k<<1|1], INF);
		V[k] = V[k<<1] * V[k<<1|1] % MOD;
	}
}
void build(int l, int r, int k){
	if(l==r){
		T[k]={l, y[l]};
		return;
	}
	int m = l+r>>1;
	build(l, m, k<<1);
	build(m+1, r, k<<1|1);
	T[k] = comb(T[k<<1], T[k<<1|1]);
}

void build2(int l, int r, int k){
	if(l==r){
		S[k] = x[l];
		V[k] = x[l];
		return;
	}
	int m = l+r>>1;
	build2(l, m, k<<1);
	build2(m+1, r, k<<1|1);
	S[k] = min(S[k<<1] * S[k<<1|1], INF);
	V[k] = V[k<<1] * V[k<<1|1] % MOD;
}

int init(int nn, int X[], int Y[]) {
	n=nn;
	for(int i = 1; i <= n; ++i){
		x[i-1]=X[i-1];
		y[i-1]=Y[i-1];
	}
	build2(0, n-1, 1);
	build(0, n-1, 1);
	int pos = T[1][0];
	return get2(0, n-1, 0, pos, 1) * y[pos] % MOD;
}

int updateX(int pos, int val) {	
	upd(0, n-1, pos, 1,val);
	UPD(0,n-1, pos, n, 1);
	int poss = T[1][0];
	return get2(0, n-1, 0, poss, 1) * y[poss] % MOD;
}

int updateY(int pos, int val) {
	upd2(0, n-1, pos, 1,val);
	int poss = T[1][0];
	return get2(0, n-1, 0, poss, 1) * y[poss] % MOD;
}

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