Submission #599167

#	Time	Username	Problem	Language	Result	Execution time	Memory
599167		Temmie	Horses (IOI15_horses)	C++17	100 / 100	191 ms	59088 KiB

horses

#include <bits/stdc++.h>

constexpr const int mod = 1e9 + 7;

int n;
std::vector <int> gr, pr;

struct Seg {
	
	struct Item {
		
		long long ans = 0;
		long long ans_mod = 0;
		long long suf = 0, sum = 0, sum_mod = 0;
		int ind = 0;
		
	};
	
	int size;
	std::vector <Item> v;
	
	Seg(int s) {
		size = 1;
		while (size < s) {
			size <<= 1;
		}
		v.resize(size << 1);
	}
	
	Item merge(Item l, Item r) {
		Item res;
		res.sum = std::min((long long) mod - 5, l.sum * r.sum);
		res.sum_mod = l.sum_mod * r.sum_mod % mod;
		if (pr[l.ind] > l.suf * r.ans){
			res.ans = l.ans;
			res.ans_mod = l.ans_mod;
			res.suf = std::min((long long) mod - 5, l.suf * r.sum);
			res.ind = l.ind;
			return res;
		} else {
			res.ans = std::min((long long) mod - 5, l.sum * r.ans);
			res.ans_mod = l.sum_mod * r.ans_mod % mod;
			res.suf = r.suf;
			res.ind = r.ind;
		}
		return res;
	}
	
	void make() {
		make(0, 0, n);
	}
	
	void make(int now, int l, int r){
		if (!(r - l - 1)) {
			v[now].ans = std::min((long long) mod - 5, (long long) gr[l] * pr[l]);
			v[now].ans_mod = (long long) gr[l] * pr[l] % mod;
			v[now].suf = 1;
			v[now].sum = v[now].sum_mod = gr[l];
			v[now].ind = l;
			return;
		}
		int mid = (l + r) >> 1;
		make(now * 2 + 1, l, mid);
		make(now * 2 + 2, mid, r);
		v[now] = merge(v[now * 2 + 1], v[now * 2 + 2]);
	}
	
	void update(int ind, long long val, bool which) {
		update(ind, val, which, 0, 0, n);
	}
	
	void update(int ind, long long val, bool which, int now, int l, int r) {
		if (!(r - l - 1)) {
			if (which) {
				gr[l] = val;
			} else {
				pr[l] = val;
			}
			v[now].ans = std::min((long long) mod - 5, (long long) gr[l] * pr[l]);
			v[now].ans_mod = (long long) gr[l] * pr[l] % mod;
			v[now].suf = 1;
			v[now].sum = v[now].sum_mod = gr[l];
			v[now].ind = l;
			return;
		}
		int mid = (l + r) >> 1;
		if (ind < mid) {
			update(ind, val, which, now * 2 + 1, l, mid);
		} else {
			update(ind, val, which, now * 2 + 2, mid, r);
		}
		v[now] = merge(v[now * 2 + 1], v[now * 2 + 2]);
	}
	
};

Seg seg(0);

int init(int _n, int _gr[], int _pr[]) {
	n = _n;
	gr.resize(n);
	pr.resize(n);
	for (int i = 0; i < n; i++) {
		gr[i] = _gr[i];
		pr[i] = _pr[i];
	}
	seg = Seg(n);
	seg.make();
	return seg.v[0].ans_mod;
}

// gr
int updateX(int pos, int val) {
	seg.update(pos, val, true);
	return seg.v[0].ans_mod;
}

// pr
int updateY(int pos, int val) {
	seg.update(pos, val, false);
	return seg.v[0].ans_mod;
}

Compilation message (stderr)

horses.cpp: In member function 'void Seg::update(int, long long int, bool, int, int, int)':
horses.cpp:75:13: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   75 |     gr[l] = val;
      |             ^~~
horses.cpp:77:13: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   77 |     pr[l] = val;
      |             ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:109:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |  return seg.v[0].ans_mod;
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:115:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |  return seg.v[0].ans_mod;
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:121:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |  return seg.v[0].ans_mod;

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