Submission #764787

#	Time	Username	Problem	Language	Result	Execution time	Memory
764787		SanguineChameleon	Horses (IOI15_horses)	C++17	100 / 100	514 ms	33924 KiB

horses

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

const int mod = 1e9 + 7;

int mul(int a, int b) {
	if (a > mod / b) {
		return mod;
	}
	else {
		return a * b;
	}
}

struct node {
	int best;
	int prod1;
	int prod2;
};

const int maxN = 5e5 + 20;
node tree[maxN * 4];
int X[maxN];
int Y[maxN];
int N;

int get(int id, int lt, int rt, int ql, int qr, int type) {
	if (lt == ql && rt == qr) {
		if (type == 1) {
			return tree[id].prod1;
		}
		else {
			return tree[id].prod2;
		}
	}
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		return get(id * 2, lt, mt, ql, qr, type);
	}
	else if (ql >= mt + 1) {
		return get(id * 2 + 1, mt + 1, rt, ql, qr, type);
	}
	else {
		if (type == 1) {
			return mul(get(id * 2, lt, mt, ql, mt, type), get(id * 2 + 1, mt + 1, rt, mt + 1, qr, type));
		}
		else {
			return 1LL * get(id * 2, lt, mt, ql, mt, type) * get(id * 2 + 1, mt + 1, rt, mt + 1, qr, type) % mod;
		}
	}
}

void merge(int id, int type) {
	if (type == 1) {
		tree[id].prod1 = mul(tree[id * 2].prod1, tree[id * 2 + 1].prod1);
		tree[id].prod2 = 1LL * tree[id * 2].prod2 * tree[id * 2 + 1].prod2 % mod;
	}
	else {
		int best_l = tree[id * 2].best;
		int best_r = tree[id * 2 + 1].best;
		if (mul(get(1, 1, N, best_l + 1, best_r, 1), Y[best_r]) > Y[best_l]) {
			tree[id].best = best_r;
		}
		else {
			tree[id].best = best_l;
		}
	}
}

void build(int id, int lt, int rt, int type) {
	if (lt == rt) {
		if (type == 1) {
			tree[id].prod1 = X[lt];
			tree[id].prod2 = X[lt];
		}
		else {
			tree[id].best = lt;
		}
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt, type);
	build(id * 2 + 1, mt + 1, rt, type);
	merge(id, type);
}

void update(int id, int lt, int rt, int pos, int type) {
	if (lt == rt) {
		if (type == 1) {
			tree[id].prod1 = X[lt];
			tree[id].prod2 = X[lt];
		}
		else {
			tree[id].best = lt;
		}
		return;
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		update(id * 2, lt, mt, pos, type);
	}
	else {
		update(id * 2 + 1, mt + 1, rt, pos, type);
	}
	merge(id, type);
}

int calc() {
	return 1LL * get(1, 1, N, 1, tree[1].best, 2) * Y[tree[1].best] % mod;
}

int init(int _N, int _X[], int _Y[]) {
	N = _N;
	for (int i = 1; i <= N; i++) {
		X[i] = _X[i - 1];
		Y[i] = _Y[i - 1];
	}
	build(1, 1, N, 1);
	build(1, 1, N, 2);
	return calc();
}

int updateX(int pos, int val) {	
	pos++;
	X[pos] = val;
	update(1, 1, N, pos, 1);
	update(1, 1, N, pos, 2);
	return calc();
}

int updateY(int pos, int val) {
	pos++;
	Y[pos] = val;
	update(1, 1, N, pos, 2);
	return calc();
}

Compilation message (stderr)

horses.cpp: In function 'int get(int, int, int, int, int, int)':
horses.cpp:49:99: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   49 |    return 1LL * get(id * 2, lt, mt, ql, mt, type) * get(id * 2 + 1, mt + 1, rt, mt + 1, qr, type) % mod;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void merge(int, int)':
horses.cpp:57:70: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   57 |   tree[id].prod2 = 1LL * tree[id * 2].prod2 * tree[id * 2 + 1].prod2 % mod;
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int calc()':
horses.cpp:110:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |  return 1LL * get(1, 1, N, 1, tree[1].best, 2) * Y[tree[1].best] % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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