Submission #247558

#	Time	Username	Problem	Language	Result	Execution time	Memory
247558		ernestvw	Horses (IOI15_horses)	C++11	0 / 100	434 ms	31328 KiB

horses

    #include <bits/stdc++.h>
    using namespace std;
     
    using ll = long long;
     
    const ll mod = 1e9 + 7;
     
    int n;
    vector<ll> C, P;
     
    ll preprod = 1;
     
    ll fp(ll x, ll y){
    	ll res=1;
    	while(y){
    		if(y%2LL)res*=x;
    		res%=mod;
    		x*=x;
    		x%=mod;
    		y/=2LL;
    	}
    	return res;
    }
     
    ll inv(ll x){return fp(x,mod-2LL);}
     
    set<int> _indices, _negindices;
     
    int prochain(int i) {
    	if(_indices.size() == 0 || i >= *_indices.rbegin()) return n;
    	return *lower_bound(_indices.begin(), _indices.end(), i + 1);
    }
     
    int precedent(int i) {
    	if(i == 0) return -1;
    	if(_negindices.size() == 0 || -i >= *_negindices.rbegin()) return 0;
    	return -*lower_bound(_negindices.begin(), _negindices.end(), -i+1);
    }
     
    ll treeProd[4000000],treeMax[4000000];
     
    void updateProd(int l, int r, int idx, int i, ll val) {
    	if(idx < l || r < idx || r < l) return;
    	if(l == r) {
    		treeProd[i] = val;
    		return;
    	}
    	updateProd(l, (l+r)/2, idx, 2*i+1, val);
    	updateProd((l+r)/2+1, r, idx, 2*i+2, val);
    	treeProd[i] = treeProd[2*i+1] * treeProd[2*i+2];
    	treeProd[i] %= mod;
    }
     
    ll getProd(int l, int r, int L, int R, int i) {
    	if(R < l || L > r || r < l) return 1;
    	if(L <= l && r <= R) return treeProd[i];
    	return (getProd(l, (l+r)/2, L, R, 2*i+1) * getProd((l+r)/2+1, r, L, R, 2*i+2)) % mod;
    }
     
    void updateMax(int l, int r, int idx, int i, ll val) {
    	if(idx < l || r < idx || r < l) return;
    	if(l == r) {
    		treeMax[i] = val;
    		return;
    	}
    	updateMax(l, (l+r)/2, idx, 2*i+1, val);
    	updateMax((l+r)/2+1, r, idx, 2*i+2, val);
    	treeMax[i] = max(treeMax[2*i+1], treeMax[2*i+2]);
    }
     
    ll getMax(int l, int r, int L, int R, int i) {
    	if(R < l || L > r || r < l) return 0;
    	if(L <= l && r <= R) return treeMax[i];
    	return max(getMax(l, (l+r)/2, L, R, 2*i+1), getMax((l+r)/2+1, r, L, R, 2*i+2));
    }
     
    int solve2() {
    	ll prod = C[n - 1];
    	int best = n - 1;
    	long double ldprod = (long double)C[n-1];
    	for(int i = n - 2; i >= 0; --i) {
    		prod *= C[i];
    		ldprod *= C[i];
    		long double x = ldprod * (long double)P[best];
    		if(x >= 1.5e18) break;
    		if(prod * P[best] <= C[i] * P[i]) {
    			best = i;
    			prod = C[i];
    			ldprod = (long double)C[i];
    		}
    	}
    	prod = 1;
    	if(n > 1000) {
    		prod = preprod;
    		for(int i = n - 100; i <= best; ++i)
    			prod = (prod * C[i]) % mod;
    		prod = (prod * P[best]) % mod;
    		return int(prod % mod);
    	}
    	for(int i = 0; i <= best; ++i) {
    		prod *= C[i];
    		prod %= mod;
    	}
    	prod *= P[best];
    	prod %= mod;
    	return int(prod % mod);
    }
     
    int solve() {
    	ll prod = C[n - 1];
    	int best = n - 1;
    	long double ldprod = (long double)C[n-1];
    	ll pbest = P[n - 1];
    	int i = precedent(n - 1);
    	while(i >= 0) {
    		prod *= C[i];
    		ldprod *= (long double)C[i];
    		ll p = getMax(0, n-1, i, prochain(i) - 1, 0);
    		long double x = ldprod * (long double)pbest;
    		if(x >= 1.5e18) break;
    		if(prod * pbest <= C[i] * p) {
    			best = i;
    			prod = C[i];
    			pbest = p;
    			ldprod = (long double)C[i];
    		}
    		i = precedent(i);
    	}
    	prod = getProd(0, n-1, 0, best, 0);
    	prod *= pbest;
    	prod %= mod;
    	return int(prod);
    }
     
    int init2(int N, int X[], int Y[]) {
    	n = N;
    	C.resize(n);
    	P.resize(n);
    	for(int i = 0; i < n; ++i) C[i] = X[i];
    	for(int i = 0; i < n; ++i) P[i] = Y[i];
    	if(n > 1000) {
    		preprod = 1;
    		for(int i = 0; i < n - 100; ++i) {
    			preprod *= C[i];
    			preprod %= mod;
    		}
    	}
    	return solve2();
    }
     
    int init(int N, int X[], int Y[]) {
    	n = N;
    	C.resize(n);
    	P.resize(n);
    	for(int i = 0; i < n; ++i) C[i] = X[i];
    	for(int i = 0; i < n; ++i) P[i] = Y[i];
    	memset(treeProd, 1, sizeof(P));
    	memset(treeMax, 0, sizeof(P));
    	for(int i = 0; i < n; ++i) {
    		updateProd(0, n - 1, i, 0, C[i]);
    		updateMax(0, n - 1, i, 0, P[i]);
    	}
     
    	for(int i = 0; i < n; ++i) {
    		//if(C[i] != 1) _indices.insert(_indices.end(), i);
    		//if(C[n-1-i] != 1) _negindices.insert(_negindices.end(), -(n-1-i));
    	}
      return 13;
     
    	return solve();
    }
     
    int updateX2(int pos, int val) {
    	if(n > 1000 && pos < n - 100) {
    		preprod *= inv(C[pos]);
    		preprod %= mod;
    		preprod *= (ll)val;
    		preprod %= mod;
    	}
    	C[pos] = val;
    	return solve2();
    }
     
    int updateX(int pos, int val) {
    	updateProd(0, n-1, pos, 0, val);
    	if(C[pos] == 1 && val != 1) _indices.insert(pos), _negindices.insert(-pos);
    	if(C[pos] != 1 && val == 1) _indices.erase(pos), _negindices.erase(-pos);
    	C[pos] = val;
    	return solve();
    }
     
    int updateY2(int pos, int val) {
    	P[pos] = val;
    	return solve2();
    }
     
    int updateY(int pos, int val) {
    	updateMax(0, n-1, pos, 0, val);
    	P[pos] = val;
    	return solve();
    }

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