Submission #387175

#	Time	Username	Problem	Language	Result	Execution time	Memory
387175		ParsaAlizadeh	Horses (IOI15_horses)	C++17	100 / 100	293 ms	72684 KiB

horses

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

#define lc (id << 1)
#define rc (lc | 1)

typedef long long ll;

struct Node {
	int ind;
	ll v1 = 1, v2 = 1;
};

int const MOD = 1e9 + 7;

int n;
vector<int> A, B;
vector<Node> mxseg;
vector<ll> valseg;

inline ll mul(ll x, ll y) {
	return x * y > MOD ? 0 : x * y;
}

Node mxmerge(Node const& l, Node const& r) {
	Node res;
	ll val = mul(l.v2, mul(r.v1, B[r.ind]));
	if (val == 0 || val >= B[l.ind]) {
		res.ind = r.ind;
		res.v1 = mul(l.v1, mul(l.v2, r.v1));
		res.v2 = r.v2;
	}
	else {
		res.ind = l.ind;
		res.v1 = l.v1;
		res.v2 = mul(l.v2, mul(r.v1, r.v2));
	}
	return res;
}

void mxbuild(int id, int l, int r, int ind) {
	if (ind != -1 && (ind < l || r <= ind))
		return;
	if (r - l == 1) {
		mxseg[id].ind = l;
		mxseg[id].v1 = A[l];
		return;
	}
	int mid = (l + r) >> 1;
	mxbuild(lc, l, mid, ind);
	mxbuild(rc, mid, r, ind);
	mxseg[id] = mxmerge(mxseg[lc], mxseg[rc]);
}

void valbuild(int id, int l, int r, int ind) {
	if (ind != -1 && (ind < l || r <= ind))
		return;
	if (r - l == 1) {
		valseg[id] = A[l];
		return;
	}
	int mid = (l + r) >> 1;
	valbuild(lc, l, mid, ind);
	valbuild(rc, mid, r, ind);
	valseg[id] = valseg[lc] * valseg[rc] % MOD;
}

ll valget(int id, int l, int r, int qr) {
	if (r <= qr)
		return valseg[id];
	if (qr <= l)
		return 1;
	int mid = (l + r) >> 1;
	return valget(lc, l, mid, qr) * valget(rc, mid, r, qr) % MOD;
}

int query() {
	int ind = mxseg[1].ind;
	return valget(1, 0, n, ind + 1) * B[ind] % MOD;
}

int init(int N, int X[], int Y[]) {
	n = N;
	A.assign(X, X + n);
	B.assign(Y, Y + n);
	mxseg.resize((n + 1) << 2);
	valseg.resize((n + 1) << 2);
	mxbuild(1, 0, n, -1);
	valbuild(1, 0, n, -1);
	return query();
}

int updateX(int pos, int val) {
	A[pos] = val;
	mxbuild(1, 0, n, pos);
	valbuild(1, 0, n, pos);
	return query();
}

int updateY(int pos, int val) {
	B[pos] = val;
	mxbuild(1, 0, n, pos);
	valbuild(1, 0, n, pos);
	return query();
}

Compilation message (stderr)

horses.cpp: In function 'int query()':
horses.cpp:80:43: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   80 |  return valget(1, 0, n, ind + 1) * B[ind] % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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