Submission #641119

#	Time	Username	Problem	Language	Result	Execution time	Memory
641119		ymm	Horses (IOI15_horses)	C++17	17 / 100	468 ms	55944 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

typedef __float128 fl;
static const int N = 1<<19;
static const int mod = 1e9+7;
static int n;

struct {
	fl mxf;
	fl lzf;
	int mxi;
	int lzi;
} __attribute__((packed)) seg[N<<1];

static void upd(int i, fl xf, int xi)
{
	seg[i].mxf += xf;
	seg[i].lzf += xf;
	seg[i].mxi = ((ll)seg[i].mxi * xi) % mod;
	seg[i].lzi = ((ll)seg[i].lzi * xi) % mod;
}

static void down(int i)
{
	upd(2*i+1, seg[i].lzf, seg[i].lzi);
	upd(2*i+2, seg[i].lzf, seg[i].lzi);
	seg[i].lzf = 0;
	seg[i].lzi = 1;
}

static void up(int i)
{
	if (seg[2*i+1].mxf > seg[2*i+2].mxf)
		seg[i] = seg[2*i+1];
	else
		seg[i] = seg[2*i+2];
}

static void add(int l, int r, fl xf, int xi, int i=0, int b=0, int e=n)
{
	if (l <= b && e <= r)
		return upd(i, xf, xi);
	if (r <= b || e <= l)
		return;
	down(i);
	add(l,r,xf,xi,2*i+1,b,(b+e)/2);
	add(l,r,xf,xi,2*i+2,(b+e)/2,e);
	up(i);
}

static void seg_init(fl xf[], int xi[], int i=0, int b=0, int e=n)
{
	if (e-b == 1) {
		seg[i] = {xf[b], 0, xi[b], 1};
		return;
	}
	seg_init(xf,xi,2*i+1,b,(b+e)/2);
	seg_init(xf,xi,2*i+2,(b+e)/2,e);
	up(i);
}

fl xf[N];
int xi[N];
int *X, *Y;

int init(int n, int X[], int Y[]) {
	xf[0] = log2((long double)X[0]); Loop (i,1,n) xf[i] = xf[i-1]+log2((double)X[i]);
	Loop (i,0,n) xf[i] += log2((long double)Y[i]);
	xi[0] = X[0]; Loop (i,1,n) xi[i] = ((ll)xi[i-1] * X[i]) % mod;
	Loop (i,0,n) xi[i] = ((ll)xi[i] * Y[i]) % mod;
	::X = X;
	::Y = Y;
	::n = n;
	seg_init(xf, xi);
	return seg[0].mxi;
}

static ll mpow(ll x, ll y){ll ans=1;while(y){ans=y&1?ans*x%mod:ans;x=x*x%mod;y>>=1;}return ans;}

int updateX(int pos, int val) {	
	add(pos, n, -log2((long double)X[pos]), mpow(X[pos], mod-2));
	X[pos] = val;
	add(pos, n, log2((long double)X[pos]), X[pos]);
	return seg[0].mxi;
}

int updateY(int pos, int val) {
	add(pos, pos+1, -log2((long double)Y[pos]), mpow(Y[pos], mod-2));
	Y[pos] = val;
	add(pos, pos+1, log2((long double)Y[pos]), Y[pos]);
	return seg[0].mxi;
}

Compilation message (stderr)

horses.cpp: In function 'void upd(int, fl, int)':
horses.cpp:26:37: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   26 |  seg[i].mxi = ((ll)seg[i].mxi * xi) % mod;
      |               ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:27:37: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   27 |  seg[i].lzi = ((ll)seg[i].lzi * xi) % mod;
      |               ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:73:30: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   73 | int init(int n, int X[], int Y[]) {
      |                          ~~~~^~~
horses.cpp:71:10: note: shadowed declaration is here
   71 | int *X, *Y;
      |          ^
horses.cpp:73:21: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   73 | int init(int n, int X[], int Y[]) {
      |                 ~~~~^~~
horses.cpp:71:6: note: shadowed declaration is here
   71 | int *X, *Y;
      |      ^
horses.cpp:73:14: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   73 | int init(int n, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:13:12: note: shadowed declaration is here
   13 | static int n;
      |            ^
horses.cpp:76:58: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   76 |  xi[0] = X[0]; Loop (i,1,n) xi[i] = ((ll)xi[i-1] * X[i]) % mod;
      |                                     ~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:77:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   77 |  Loop (i,0,n) xi[i] = ((ll)xi[i] * Y[i]) % mod;
      |                       ~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:88:46: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   88 |  add(pos, n, -log2((long double)X[pos]), mpow(X[pos], mod-2));
      |                                          ~~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:95:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   95 |  add(pos, pos+1, -log2((long double)Y[pos]), mpow(Y[pos], mod-2));
      |                                              ~~~~^~~~~~~~~~~~~~~

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