Submission #289989

#	Time	Username	Problem	Language	Result	Execution time	Memory
289989		Berted	Horses (IOI15_horses)	C++14	100 / 100	1318 ms	46200 KiB

horses

#include "horses.h"
#include <iostream>
#include <algorithm>
#include <utility>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second

const int SZ = (1 << 20) + 5;
const ll MD = 1e9 + 7;

using namespace std;

int n;
ll x[500001], y[500001];

namespace segX
{
	pii seg[SZ];
	
	inline pii merge(const pii &L, const pii &R)
	{
		pii ret;
		ret.fst = min(MD, L.fst * R.fst);
		ret.snd = (L.snd * R.snd) % MD;
		return ret;
	}

	void build(int idx, int L, int R)
	{
		seg[idx] = {1, 1};
		if (L <= R)
		{
			if (L == R) {seg[idx] = {x[L], x[R]};}
			else
			{
				int M = L + R >> 1;
				build(idx << 1, L, M);
				build(idx << 1 | 1, M + 1, R);
				seg[idx] = merge(seg[idx << 1], seg[idx << 1 | 1]);
			} 
		}
	}

	void update(int idx, int L, int R, int x, int v)
	{
		if (L <= R)
		{
			if (L == x && x == R) {seg[idx] = {v, v};}
			else
			{
				int M = L + R >> 1;
				if (x <= M) {update(idx << 1, L, M, x, v);}
				else {update(idx << 1 | 1, M + 1, R, x, v);}
				seg[idx] = merge(seg[idx << 1], seg[idx << 1 | 1]);
			}
		}
	}

	pii query(int idx, int L, int R, int l, int r)
	{
		l = max(L, l); r = min(R, r);
		if (l <= r)
		{
			if (L == l && R == r) {return seg[idx];}
			else
			{
				int M = L + R >> 1;
				return merge(query(idx << 1, L, M, l, r), query(idx << 1 | 1, M + 1, R, l, r));
			}
		}
		return {1, 1};
	}
}

namespace segY
{
	int seg[SZ];

	inline int merge(const int &L, const int &R)
	{
		if (L == -1) {return R;}
		if (R == -1) {return L;}
		if (y[R] * segX::query(1, 0, n - 1, L + 1, R).fst >= y[L]) {return R;}
		else {return L;}
	}

	void build(int idx, int L, int R)
	{
		seg[idx] = -1;
		if (L <= R)
		{
			if (L == R) {seg[idx] = L;}
			else
			{
				int M = L + R >> 1;
				build(2 * idx, L, M);
				build(2 * idx + 1, M + 1, R);
				seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]);
			}
		}
	}

	void update(int idx, int L, int R, int x)
	{
		if (L < R)
		{
			int M = L + R >> 1;
			if (x <= M) {update(2 * idx, L, M, x);}
			else {update(2 * idx + 1, M + 1, R, x);}
			seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]);
		}
	}
}

inline ll eval(int idx) {return y[idx] * segX::query(1, 0, n - 1, 0, idx).snd % MD;}


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];}
	segX::build(1, 0, n - 1);
	segY::build(1, 0, n - 1);
	return eval(segY::seg[1]);
}

int updateX(int pos, int val) 
{
	segX::update(1, 0, n - 1, pos, val);
	segY::update(1, 0, n - 1, pos);	
	return eval(segY::seg[1]);
}

int updateY(int pos, int val) 
{
	y[pos] = val;
	segY::update(1, 0, n - 1, pos);
	return eval(segY::seg[1]);
}

Compilation message (stderr)

horses.cpp: In function 'void segX::build(int, int, int)':
horses.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int M = L + R >> 1;
      |             ~~^~~
horses.cpp: In function 'void segX::update(int, int, int, int, int)':
horses.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int M = L + R >> 1;
      |             ~~^~~
horses.cpp: In function 'std::pair<long long int, long long int> segX::query(int, int, int, int, int)':
horses.cpp:69:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int M = L + R >> 1;
      |             ~~^~~
horses.cpp: In function 'void segY::build(int, int, int)':
horses.cpp:97:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |     int M = L + R >> 1;
      |             ~~^~~
horses.cpp: In function 'void segY::update(int, int, int, int)':
horses.cpp:109:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |    int M = L + R >> 1;
      |            ~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:126:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  126 |  return eval(segY::seg[1]);
      |         ~~~~^~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:133:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |  return eval(segY::seg[1]);
      |         ~~~~^~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:140:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  140 |  return eval(segY::seg[1]);
      |         ~~~~^~~~~~~~~~~~~~

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