Submission #396822

#	Time	Username	Problem	Language	Result	Execution time	Memory
396822		Kenzo_1114	Horses (IOI15_horses)	C++17	0 / 100	495 ms	54492 KiB

horses

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
const long long int MOD = 1e9 + 7;

int n;
long long int x[MAXN], y[MAXN];
long long int seg[2][4 * MAXN];
set<int> s;

void upd(bool f, int pos, int bg, int ed, int id, int val)
{
	if(bg == ed){	seg[f][pos] = (!f) ? val : id; return; }

	int mid = (bg + ed) >> 1, l = 2 * pos, r = l + 1;

	if(id <= mid)	upd(f, l, bg, mid, id, val);
	else 			upd(f, r, mid + 1, ed, id, val);

	if(!f)	seg[f][pos] = (seg[f][l] * seg[f][r]) % MOD;
	else	seg[f][pos] = (y[seg[f][l]] > y[seg[f][r]]) ? seg[f][l] : seg[f][r];
}

int qry(bool f, int pos, int bg, int ed, int p, int q)
{
	if(q < p || q < bg || ed < p)	return (!f) ? 1 : 0;
	if(p <= bg && ed <= q)			return seg[f][pos];

	int mid = (bg + ed) >> 1, l = 2 * pos, r = l + 1;

	if(!f)	return (qry(f, l, bg, mid, p, q) * qry(f, r, mid + 1, ed, p, q)) % MOD;

	l = qry(f, l, bg, mid, p, q);
	r = qry(f, r, mid + 1, ed, p, q);
	return (y[l] > y[r]) ? l : r;
}

int getAns()
{
	set<int> :: iterator l, r;
	int k = 0;

	l = s.end();
	while(k < 32 && l != s.begin())	k++, l--;

	r = l;	r++;
	int i = 0;
	long long int prefX = 1;
	while(r != s.end())
	{
//		printf("i = %d l = %d r = %d | ", i, *l, *r);
		int q = qry(1, 1, 1, n, *l + 1, *r - 1);
		if(q)	i = q;
		prefX *= x[*r];
//		printf("i = %d l = %d r = %d\n", i, *l, *r);

		if(prefX >= MOD || y[i] < prefX * y[*r])
		{
			prefX = 1;
			i = *r;
		}

		l++, r++;
	}

//	printf("i = %d\n", i);

	return (qry(0, 1, 1, n, 1, i) * y[i]) % MOD;
}

int updateX(int id, int val)
{
	id++;
	if(val > 1)	s.insert(id);
	else		s.erase(id);
	x[id] = val;
	upd(0, 1, 1, n, id, val);

	return getAns();
}

int updateY(int id, int val)
{
	id++;
	y[id] = val;
	upd(1, 1, 1, n, id, val);

	return getAns();
}

int init(int N, int X[], int Y[])
{
	n = N;
	for(int i = n; i > 0; i--)	x[i] = X[i - 1];
	for(int i = n; i > 0; i--)	y[i] = Y[i - 1];

	for(int i = 1; i <= n; i++)	
	{
		upd(0, 1, 1, n, i, x[i]);
		upd(1, 1, 1, n, i, y[i]);
		if(x[i] > 1)	s.insert(i);
	}
	s.insert(0);
	s.insert(n + 1);

	return getAns();
}

Compilation message (stderr)

horses.cpp: In function 'int qry(bool, int, int, int, int, int)':
horses.cpp:27:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   27 |  if(p <= bg && ed <= q)   return seg[f][pos];
      |                                  ~~~~~~~~~~^
horses.cpp:31:74: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   31 |  if(!f) return (qry(f, l, bg, mid, p, q) * qry(f, r, mid + 1, ed, p, q)) % MOD;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int getAns()':
horses.cpp:68:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   68 |  return (qry(0, 1, 1, n, 1, i) * y[i]) % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:99:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |   upd(0, 1, 1, n, i, x[i]);
      |                      ~~~^
horses.cpp:100:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  100 |   upd(1, 1, 1, n, i, y[i]);
      |                      ~~~^

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