Submission #1018612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018612		AmirAli_H1	Horses (IOI15_horses)	C++17	100 / 100	794 ms	29524 KiB

horses

// In the name of Allah

#include <bits/stdc++.h>
#include "horses.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct node {
	int mul, mx, ind;
};

const int maxn = (1 << 19) + 4;
const int maxlg = 20;
const int mod = 1e9 + 7;

int n; pll A[maxn];
node t[2 * maxn], ca;
int R; ll valx, lst;

node f(node a, node b) {
	node res;
	res.mul = 1ll * a.mul * b.mul % mod;
	res.mx = max(a.mx, b.mx);
	res.ind = max(a.ind, b.ind);
	return res;
}

pii fx(pii a, pii b) {
	return Mp(max(a.F, b.F), max(a.S, b.S));
}

void build(int v, int tl, int tr) {
	if (tr - tl == 1) {
		t[v].mul = A[tl].F; t[v].mx = A[tl].S;
		if (A[tl].F == 1) t[v].ind = -1;
		else t[v].ind = tl;
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void upd(int v, int tl, int tr, int i) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v].mul = A[tl].F; t[v].mx = A[tl].S;
		if (A[tl].F == 1) t[v].ind = -1;
		else t[v].ind = tl;
		return ;
	}
	int mid = (tl + tr) / 2;
	upd(2 * v + 1, tl, mid, i); upd(2 * v + 2, mid, tr, i);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

pll get_res(int v, int tl, int tr, int l, int r) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return Mp(ca.mx, ca.ind);
	if (l == tl && r == tr) return Mp(t[v].mx, t[v].ind);
	int mid = (tl + tr) / 2;
	return fx(get_res(2 * v + 1, tl, mid, l, r), get_res(2 * v + 2, mid, tr, l, r));
}

int get_mul(int v, int tl, int tr, int r) {
	r = min(r, tr);
	if (r <= tl) return ca.mul;
	if (r == tr) return t[v].mul;
	int mid = (tl + tr) / 2;
	if (r <= mid) return get_mul(2 * v + 1, tl, mid, r);
	else return 1ll * t[2 * v + 1].mul * get_mul(2 * v + 2, mid, tr, r) % mod;
}

ll get_ans(int ind) {
	if (ind >= R) {
		ll mx = 1; int j = n;
		while (j > 0) {
			pll res = get_res(0, 0, n, 0, j);
			int k = res.S;
			if (k == -1) {
				mx = max(mx, res.F); j = 0;
			}
			else {
				res = get_res(0, 0, n, k, j);
				mx = max(mx, (ll) res.F) * A[k].F; j = k;
				if (mx >= 1e9) break;
			}
		}
		R = j; valx = mx % mod;
	}
	return valx * get_mul(0, 0, n, R) % mod;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++) A[i] = Mp(X[i], Y[i]);
	ca.mul = 1; ca.mx = 0; ca.ind = -1;
	build(0, 0, n); R = -1;
	return lst = get_ans(n);
}

int updateX(int i, int val) {
	if (A[i].F == val) return lst;
	A[i].F = val;
	upd(0, 0, n, i);
	return lst = get_ans(i);
}

int updateY(int i, int val) {
	if (A[i].S == val) return lst;
	A[i].S = val;
	upd(0, 0, n, i);
	return lst = get_ans(i);
}

Compilation message (stderr)

horses.cpp: In function 'node f(node, node)':
horses.cpp:42:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |  res.mul = 1ll * a.mul * b.mul % mod;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:17:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 | #define  F      first
      |                 ^
horses.cpp:54:20: note: in expansion of macro 'F'
   54 |   t[v].mul = A[tl].F; t[v].mx = A[tl].S;
      |                    ^
horses.cpp:18:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 | #define  S      second
      |                 ^
horses.cpp:54:39: note: in expansion of macro 'S'
   54 |   t[v].mul = A[tl].F; t[v].mx = A[tl].S;
      |                                       ^
horses.cpp: In function 'void upd(int, int, int, int)':
horses.cpp:17:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   17 | #define  F      first
      |                 ^
horses.cpp:67:20: note: in expansion of macro 'F'
   67 |   t[v].mul = A[tl].F; t[v].mx = A[tl].S;
      |                    ^
horses.cpp:18:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 | #define  S      second
      |                 ^
horses.cpp:67:39: note: in expansion of macro 'S'
   67 |   t[v].mul = A[tl].F; t[v].mx = A[tl].S;
      |                                       ^
horses.cpp: In function 'int get_mul(int, int, int, int)':
horses.cpp:91:70: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  else return 1ll * t[2 * v + 1].mul * get_mul(2 * v + 2, mid, tr, r) % mod;
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'll get_ans(int)':
horses.cpp:18:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   18 | #define  S      second
      |                 ^
horses.cpp:99:16: note: in expansion of macro 'S'
   99 |    int k = res.S;
      |                ^
horses.cpp:106:9: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  106 |     if (mx >= 1e9) break;
      |         ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:119:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |  return lst = get_ans(n);
      |         ~~~~^~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:123:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  123 |  if (A[i].F == val) return lst;
      |                            ^~~
horses.cpp:126:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  126 |  return lst = get_ans(i);
      |         ~~~~^~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:130:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  130 |  if (A[i].S == val) return lst;
      |                            ^~~
horses.cpp:133:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  133 |  return lst = get_ans(i);
      |         ~~~~^~~~~~~~~~~~

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