Submission #583334

#	Time	Username	Problem	Language	Result	Execution time	Memory
583334		Drew_	Horses (IOI15_horses)	C++17	17 / 100	19 ms	10776 KiB

horses

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

#define pb push_back

using ll = long long;

const int MAX = 5e3 + 69;
const ll inf = 1e9 + 5;
const int mod = 1e9 + 7;

template<int MOD = mod>
struct Mint
{
    int val;

    Mint() : val(0) {}
    Mint(int64_t _val) : val((int)(_val % MOD)) { if (val < 0) val += MOD; }

    Mint& operator+= (const Mint &rhs) { val += rhs.val; if (val >= MOD) val -= MOD; return *this; }
    Mint& operator-= (const Mint &rhs) { val -= rhs.val; if (val < 0) val += MOD; return *this; }
    Mint& operator*= (const Mint &rhs) { val = (int)(1ll * val * rhs.val % MOD); return *this; }

    friend Mint fpow(Mint x, int64_t y)
    {
        Mint res = 1;
        for (; y > 0; y >>= 1, x *= x)
        {
            if (y & 1)
                res *= x;
        }
        return res;
    }
    friend Mint inverse(Mint x) { return fpow(x, MOD-2); }
    Mint& operator/= (const Mint &rhs) { return *this *= inverse(rhs); }

    friend Mint operator+ (Mint a, const Mint &b) { return a += b; }
    friend Mint operator- (Mint a, const Mint &b) { return a -= b; }
    friend Mint operator- (Mint a) { return 0 - a; }
    friend Mint operator* (Mint a, const Mint &b) { return a *= b; }
    friend Mint operator/ (Mint a, const Mint &b) { return a /= b; }
    friend ostream& operator<< (ostream &os, const Mint &a) { return os << a.val; }
    friend bool operator== (const Mint &a, const Mint &b) { return a.val == b.val; }
    friend bool operator!= (const Mint &a, const Mint &b) { return a.val != b.val; }
};

struct Segtree1
{
	int n;
	Mint<> st[2 * MAX];

	Segtree1() {}
	Segtree1(int n_, int ar[]) : n(n_)
	{
		for (int i = 0; i < n; ++i)
			st[i+n] = ar[i];
		for (int i = n-1; i >= 0; --i)
			st[i] = st[i << 1] * st[i << 1 | 1];
	}

	inline void modify(int p, int val)
	{
		for (st[p += n] = val; p > 1; p >>= 1)
			st[p >> 1] = st[p] * st[p^1];
	}

	inline Mint<> query(int l, int r)
	{
		Mint<> res = 1;
		for (l += n, r += n+1; l < r; l >>= 1, r >>= 1)
		{
			if (l & 1) res *= st[l++];
			if (r & 1) res *= st[--r];
		}
		return res;
	}
} st1;

struct Segtree2
{
	int n;
	int st[2 * MAX];

	Segtree2() {}
	Segtree2(int n_, int ar[]) : n(n_)
	{
		for (int i = 0; i < n; ++i)
			st[i+n] = ar[i];
		for (int i = n-1; i >= 0; --i)
			st[i] = max(st[i << 1], st[i << 1 | 1]);
	}

	inline void modify(int p, int val)
	{
		for (st[p += n] = val; p > 1; p >>= 1)
			st[p >> 1] = max(st[p], st[p^1]);
	}

	inline int query(int l, int r)
	{
		int res = 0;
		for (l += n, r += n+1; l < r; l >>= 1, r >>= 1)
		{
			if (l & 1) res = max(res, st[l++]);
			if (r & 1) res = max(res, st[--r]);
		}
		return res;
	}
} st2;


int N, X[MAX], Y[MAX];
set<int, greater<int>> non_one; // position of non-one numbers

int calc()
{
	vector<int> idx = { N };
	{
		ll val = 1;
		for (int x : non_one)
		{
			idx.pb(x);
			val *= X[x];

			if (val > inf)
				break;
		}

		if (val <= inf && idx.back() != 0)
			idx.pb(0);
	}
	reverse(idx.begin(), idx.end());

	ll mx = 0; int best = 0, ybest = 0;
	for (int i = 0; i+1 < (int)idx.size(); ++i)
	{
		int ymax = st2.query(idx[i], idx[i+1] - 1);
		ll xval = st1.query(idx[1], idx[i]).val;
			
		// cerr << idx[i] << " " << idx[i+1] << " " << xval << " " << ymax << '\n';

		if (ymax * xval > mx)
			mx = ymax * xval, best = i, ybest = ymax;
	}
	// cerr << "best: " << best << '\n';
	// cerr << '\n';

	return (st1.query(0, idx[best]) * ybest).val;
}

int init(int n, int x[], int y[])
{
	N = n;
	for (int i = 0; i < N; ++i)
		X[i] = x[i], Y[i] = y[i];

	st1 = Segtree1(n, x);
	st2 = Segtree2(n, y);

	for (int i = 0; i < N; ++i) if (x[i] != 1)
		non_one.insert(i);

	return calc();
}

int updateX(int pos, int val) 
{
	st1.modify(pos, val);
	if (val == 1) non_one.erase(pos);
	else non_one.insert(pos);

	return calc();
}

int updateY(int pos, int val) 
{
	st2.modify(pos, val);	
	return calc();
}

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