Submission #1186494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186494		harvsftw	Horses (IOI15_horses)	C++20	17 / 100	971 ms	36848 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"
using namespace std;

#define MOD (1'000'000'000 + 7)
#define F(i, n) for(int i = 0; i < (n); i++)
#define F_reverse(i, n) for(int i = (n - 1); i >= 0; i--)

int N;
int X[500000], Y[500000];
set<int> idx_with_2plus;
struct segtree {
    int segtree[1 << 21];
    int segtree_size = 1;

    const int zero = 0;
    void init(int n) {
        segtree_size = 1;
        while(segtree_size < n) {
            segtree_size <<= 1;
        }
        F(i, 2 * segtree_size) {
            segtree[i] = zero;
        }
    }
    int add(int a, int b) {
        return max(a, b);
    }
 
    int get(int i, int window_l, int window_r, int l, int r) {
        if(l <= window_l && window_r <= r) {
            return segtree[i];
        } else if((window_l <= l && l <= window_r) || (window_l <= r && r <= window_r)) {
            int m = (window_l + window_r) / 2;
            return add(get(i * 2 + 0, window_l,m,l,r), get(i * 2 + 1,m + 1,window_r,l,r));
        } else {
            return zero;
        }
    }
 
    int get(int l, int r) {
        if(l > r) {
            return zero;
        }
        return get(1, 0, segtree_size - 1, l, r);
    }
 
    void set(int i, int data) {
        i += segtree_size;
        segtree[i] = data;
        i /= 2;
        while(i > 0) {
            segtree[i] = add(segtree[i * 2 + 0], segtree[i * 2 + 1]);
            i /= 2;
        }
    }
} ohio;

int64_t mod_pow(int64_t a, int64_t b) {
	if(b == 0) {
		return 1;
	} else {
		int64_t m = mod_pow(a, b / 2);
		if(b & 1) {
			return m * m % MOD * a % MOD;
		} else {
			return m * m % MOD;
		}
	}
}

int64_t mod_inv(int64_t a) {
	return mod_pow(a, MOD - 2);
}

int64_t prod_all = 1;
int solve() {
	__int128_t h = 1;

	bool overflow = false;
	int64_t ans = prod_all;
	int prv = N;
	for(auto it = idx_with_2plus.rbegin(); it != idx_with_2plus.rend(); --it) {
		int i = *it;
		ans = ans * mod_inv(X[i]) % MOD; 

		int best_Y = ohio.get(i, prv - 1);
		if(best_Y > h) { // replace running product
			h = best_Y;
		}
		h *= X[i];
		
		prv = i;


		if(h >= 1'000'000'000) {
			overflow = true;
			h %= MOD;
			break;
		}
	}

	if(!overflow) {
		// edge case: remaining X are 1s
		assert(ans == 1);
		int best_Y = ohio.get(0, prv - 1);
		if(best_Y > h) {
			h = best_Y;
		}
	}

	return ans * h % MOD;
}

int init(int _N, int _X[], int _Y[]) {
	N = _N;
	ohio.init(N);

	F(i, N) {
		X[i] = _X[i];
		prod_all = prod_all * X[i] % MOD;
		if(X[i] > 1) {
			idx_with_2plus.insert(i);
		}

		Y[i] = _Y[i];
		ohio.segtree[ohio.segtree_size + i] = Y[i];
	}
	F_reverse(i, ohio.segtree_size) {
		ohio.segtree[i] = max(ohio.segtree[i * 2 + 0], ohio.segtree[i * 2 + 1]);
	}

	return solve();
}

int updateX(int pos, int val) {
	if(X[pos] > 1 && val == 1) {
		idx_with_2plus.erase(pos);
	} else if(X[pos] == 1 && val > 1) {
		idx_with_2plus.insert(pos);
	}

	prod_all = prod_all * mod_inv(X[pos]) % MOD;
	X[pos] = val;
	prod_all = prod_all * val % MOD;

	return solve();
}

int updateY(int pos, int val) {
	Y[pos] = val;
	ohio.set(pos, val);
	return solve();
}

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