Submission #785152

#	Time	Username	Problem	Language	Result	Execution time	Memory
785152		ymm	Horses (IOI15_horses)	C++17	100 / 100	243 ms	66668 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

namespace seg {
	const int mod = 1e9+7;
	const int N = 500010;
	int sz;
	struct {
		ll Xs, mxXs, mx;
		ll mxy;
		bool of;
	} t[N*4];
	ll X[N], Y[N];

	void merge(int i) {
		auto &t = seg::t[i], &l = seg::t[2*i+1], &r = seg::t[2*i+2];
		t.Xs = l.Xs * r.Xs % mod;
		if (r.of) {
			t.of = 1;
			t.mx = l.Xs * r.mx % mod;
			t.mxXs = r.mxXs;
			t.mxy = r.mxy;
			return;
		}
		if (l.mxy < l.mxXs * r.mx) {
			t.mx = l.Xs * r.mx;
			t.of = t.mx >= mod || l.of;
			t.mx %= mod;
			t.mxXs = r.mxXs;
			t.mxy = r.mxy;
		} else {
			t.mx = l.mx;
			t.of = l.of;
			t.mxXs = l.mxXs * r.Xs;
			t.mxy = l.mxy;
		}
	}

	void init(int i, int b, int e) {
		t[i].mx = t[i].Xs = t[i].mxXs = t[i].mxy = 1;
		t[i].of = 0;
		if (e-b == 1) {
			X[b] = Y[b] = 1;
		} else {
			init(2*i+1, b, (b+e)/2);
			init(2*i+2, (b+e)/2, e);
		}
	}
	void init(int n) { sz = n; init(0, 0, n); }

	void up(int p, int i, int b, int e) {
		if (e-b == 1) {
			t[i].Xs = X[b];
			t[i].mxXs = 1;
			t[i].mxy = Y[b];
			t[i].mx = X[b] * Y[b];
			t[i].of = t[i].mx >= mod;
			t[i].mx %= mod;
			return;
		}
		if (p < (b+e)/2)
			up(p, 2*i+1, b, (b+e)/2);
		else
			up(p, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void up(int p) { up(p, 0, 0, sz); }
}

int init(int N, int X[], int Y[]) {
	seg::init(N);
	Loop (i,0,N) {
		seg::X[i] = X[i];
		seg::Y[i] = Y[i];
		seg::up(i);
	}
	return seg::t[0].mx;
}

int updateX(int pos, int val) {	
	seg::X[pos] = val;
	seg::up(pos);
	return seg::t[0].mx;
}

int updateY(int pos, int val) {
	seg::Y[pos] = val;
	seg::up(pos);
	return seg::t[0].mx;
}

Compilation message (stderr)

horses.cpp: In function 'void seg::merge(int)':
horses.cpp:19:9: warning: declaration of 't' shadows a global declaration [-Wshadow]
   19 |   auto &t = seg::t[i], &l = seg::t[2*i+1], &r = seg::t[2*i+2];
      |         ^
horses.cpp:15:4: note: shadowed declaration is here
   15 |  } t[N*4];
      |    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:78:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   78 |   seg::up(i);
      |           ^
horses.cpp:80:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   80 |  return seg::t[0].mx;
      |         ~~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:86:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   86 |  return seg::t[0].mx;
      |         ~~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:92:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   92 |  return seg::t[0].mx;
      |         ~~~~~~~~~~^~

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