Submission #17428

#	Time	Username	Problem	Language	Result	Execution time	Memory
17428		austin990301	Horses (IOI15_horses)	C++14	54 / 100	455 ms	102768 KiB

horses

#pragma GCC optimize ("O3")
#pragma comment(linker , "/STACK:102400000,102400000")

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxN = 500000 + 10;
const LL mod = 1000000007LL;

struct Segt {
        static Segt *pmem , mem[maxN<<2];
        Segt *lc , *rc;
        int l , r;
        LL x;
        double log_x , log_y;

        Segt() {}
        Segt(int l0 , int r0) : l(l0) , r(r0) , x(1LL) , log_x(0.0) , log_y(0.0) {}
} Segt::mem[maxN<<2] , *Segt::pmem = Segt::mem;

Segt *tr;
LL Y[maxN];
int best_ans_pos;
double best_log_ans;

Segt* build(int l , int r) {
        Segt *tr = new (Segt::pmem++) Segt(l , r);

        if(l != r) {
                int m = (l+r)/2;

                tr->lc = build(l , m);
                tr->rc = build(m+1 , r);
        }

        return tr;
}

void modify_x(Segt *tr , int p , LL x) {
        int l = tr->l , r = tr->r;
        int m = (l+r)/2;

        if(l == r) {
                tr->x = x;
                tr->log_x = log(static_cast<double>(x));

                return;
        }

        if(p <= m) modify_x(tr->lc , p , x);
        else modify_x(tr->rc , p , x);

        tr->x = (tr->lc->x*tr->rc->x)%mod;
        tr->log_x = tr->lc->log_x+tr->rc->log_x;
}

void modify_y(Segt *tr , int p , LL y) {
        int l = tr->l , r = tr->r;
        int m = (l+r)/2;

        if(l == r) {
                tr->log_y = log(static_cast<double>(y));

                return;
        }

        if(p <= m) modify_y(tr->lc , p , y);
        else modify_y(tr->rc , p , y);

        tr->log_y = max(tr->lc->log_y , tr->rc->log_y);
}

void query_best_ans_pos(Segt *tr , double tmp) {
        if(tr->l == tr->r) {
                if(tmp+tr->log_x+tr->log_y > best_log_ans) {
                        best_log_ans = tmp+tr->log_x+tr->log_y;
                        best_ans_pos = tr->l;
                }

                return;
        }

        query_best_ans_pos(tr->rc , tmp+tr->lc->log_x);

        if(tmp+tr->lc->log_x+tr->lc->log_y > best_log_ans) query_best_ans_pos(tr->lc , tmp);
}

LL query_x(Segt *tr , int p) {
        int l = tr->l , r = tr->r;
        int m = (l+r)/2;
        LL res;

        if(r <= p) return tr->x;

        res = query_x(tr->lc , p);
        if(m+1 <= p) (res *= query_x(tr->rc , p)) %= mod;

        return res;
}

int init(int N , int x[] , int y[]) {
	tr = build(0 , N-1);

	for(int i = 0; i < N; i++) modify_x(tr , i , x[i]);

	for(int i = 0; i < N; i++) {
		Y[i] = static_cast<LL>(y[i]);

		modify_y(tr , i , Y[i]);
	}

	best_ans_pos = 0;
        	best_log_ans = 0.0;

        	query_best_ans_pos(tr , 0.0);

        	return static_cast<int>(query_x(tr , best_ans_pos)*Y[best_ans_pos]%mod);
}

int updateX(int pos , int val) {
	modify_x(tr , pos , static_cast<LL>(val));

	best_ans_pos = 0;
        	best_log_ans = 0.0;

        	query_best_ans_pos(tr , 0.0);

        	return static_cast<int>(query_x(tr , best_ans_pos)*Y[best_ans_pos]%mod);
}

int updateY(int pos , int val) {
	Y[pos] = static_cast<LL>(val);

	modify_y(tr , pos , Y[pos]);

	best_ans_pos = 0;
        	best_log_ans = 0.0;

        	query_best_ans_pos(tr , 0.0);

        	return static_cast<int>(query_x(tr , best_ans_pos)*Y[best_ans_pos]%mod);
}

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