Submission #1248769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248769		KindaGoodGames	Horses (IOI15_horses)	C++20	37 / 100	1022 ms	37800 KiB

horses

#include<bits/stdc++.h>
#include "horses.h"

using namespace std;
#define pii pair<int,int>
#define int long long

int mod = 1e9+7;
const int STEPS = 40; 
struct Node{
	int prod = 1;
	int large = 0;

	Node(){}
	Node(int v){
		prod = v;
		large = v > 1;
	}
	Node(int p, int l){
		prod = p;
		large = l;
	}
};
Node comb(Node a, Node b){
	return Node((a.prod*b.prod)%mod,a.large+b.large);
}
struct SegmentTree{
	int len = 1;
	vector<Node> S;
	SegmentTree(){}
	SegmentTree(int n){
		while(len < n) len <<= 1;
		S.resize(2*len, Node(1));
	}

	Node query(int ql, int qr, int l= 0, int r = -2, int i = 1){
		if(r == -2) r = len;
		if(ql <= l && r <= qr) return S[i];
		if(r <= ql || qr <= l) return Node(1);

		int mid = (l+r)/2;
		return comb(query(ql,qr,l,mid,i*2), query(ql,qr,mid,r,i*2+1));
	}

	void upd(int i, int v){
		i += len;
		S[i] = v;

		for(i /= 2; i > 0; i /= 2){
			S[i] = comb(S[i*2], S[i*2+1]);
		}
	}

	int search(int v){
		int i = 1;
		if(v > S[i].large) return -1;
		
		while(i < len){
			if(S[i*2+1].large >= v){
				i = i*2+1;
			} else{
				v -= S[i*2+1].large;
				i = i*2;
			}
		}
		return i-len;
	}
};
struct SegmentTreeMax{
	vector<int> S;
	int len = 1;
	SegmentTreeMax(int n){
		while(len < n) len <<= 1;
		S.resize(2*len);
	}
	SegmentTreeMax(){}

	int query(int ql, int qr, int l = 0, int r = -2, int i = 1){
		if(r == -2) r = len;
		if(ql <= l && r <= qr) return S[i];
		if(r <= ql || qr <= l) return 0;

		int mid = (l+r)/2;
		return max(query(ql,qr,l,mid,i*2), query(ql,qr,mid,r,i*2+1));
	}

	void upd(int i, int v){
		i += len;
		S[i] = v;
		for(i /= 2; i > 0; i /= 2){
			S[i] = max(S[i*2], S[i*2+1]);
		}
	}
};
int n;

vector<int> X;
vector<int> Y;
SegmentTree seg;
SegmentTreeMax segY;
int res = 0;

int solve(){
	set<int> candidates;
	for(int i = 1; i <= STEPS; i++){
		// last pos with >= k 1s

		int l = 0; int r = n-1;
		int b = seg.search(i); 
		candidates.insert(b);
	}
	candidates.erase(-1);
	vector<int> cand(candidates.begin(),candidates.end());
	cand.push_back(n);

	int cur = seg.query(0,cand[0]).prod;

	for(int I = 0; I < cand.size()-1; I++){
		int i = cand[I];
		int coefI = segY.query(i, cand[I+1]+1);

		cur *= X[i];
		cur %= mod;
		int c = 1;
		bool valid = false;
		for(int J = I+1; J < cand.size()-1; J++){
			int j = cand[J];

			c *= X[j];

			int coefJ = segY.query(j, cand[J+1]+1);
			if(c > coefI || c *coefJ > coefI){
				valid = true; 
				break;
			}
		}

		if(!valid){ 
			res = (cur * coefI)% mod;
			return res;
		}
	}   

	res = segY.query(0, n+1)%mod;
	return res;
}

int32_t init(int32_t N, int32_t mult[], int32_t cost[]) {
	n = N;
	X.resize(n);
	Y.resize(n);
	seg = SegmentTree(n);
	segY = SegmentTreeMax(n);
	for(int i = 0; i < n; i++){
		X[i] = mult[i];
		Y[i] = cost[i];
	} 
	for(int i = 0;i < n; i++){
		seg.upd(i, X[i]);
		segY.upd(i, Y[i]);
	} 

	return solve();
}

int32_t updateX(int32_t pos, int32_t val) {	
	X[pos] = val;
	seg.upd(pos,val);

	return solve();
}

int32_t updateY(int32_t pos, int32_t val) {
	Y[pos] = val;
	segY.upd(pos,val);

	
	return solve();
}

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