Submission #485606

#	Time	Username	Problem	Language	Result	Execution time	Memory
485606		MilosMilutinovic	Horses (IOI15_horses)	C++14	0 / 100	19 ms	14708 KiB

horses

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
const ll mod2=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

ll mul(ll a, ll b) {
	return a*b%mod;
}

const int N=201000;
int a[N],b[N];
ll ps[N],pp[N];

struct node {
	db mx,lzy;
	ll f,lzyp;
}nd[4*N];

void upd(int p) {
	if (nd[p+p].mx>nd[p+p+1].mx) {
		nd[p]=nd[p+p];
	} else {
		nd[p]=nd[p+p+1];
	}
}

void push(int p) {
	nd[p].mx+=nd[p].lzy;
	nd[p].f=mul(nd[p].f,nd[p].lzyp);
	nd[p+p].lzy+=nd[p].lzy;
	nd[p+p+1].lzy+=nd[p].lzy;
	nd[p+p].lzyp=mul(nd[p+p].lzyp,nd[p].lzyp);
	nd[p+p+1].lzyp=mul(nd[p+p+1].lzyp,nd[p].lzyp);
	nd[p].lzy=0;
	nd[p].lzyp=1;
}

void build(int p,int l,int r) {
	nd[p].lzyp=1;
	if (l==r) {
		nd[p].mx=ps[l]+log10(b[l]);
		nd[p].f=mul(pp[l],b[l]);
		return;
	}
	int md=l+r>>1;
	build(p+p,l,md);
	build(p+p+1,md+1,r);
	upd(p);
}

void modify(int p,int l,int r,int ql,int qr,db x,ll y) {
	push(p);
	if (l>qr||r<ql) return;
	if (ql<=l&&r<=qr) {
		nd[p].lzy+=x;
		nd[p].lzyp=mul(nd[p].lzyp,y);
		push(p);
		return;
	}
	int md=l+r>>1;
	modify(p+p,l,md,ql,qr,x,y);
	modify(p+p+1,md+1,r,ql,qr,x,y);
	upd(p);
}

ll init(int n,int* x,int* y) {
	ps[0]=0; pp[0]=1;
	rep(i,1,n+1) ps[i]=ps[i-1]+log10(x[i]);
	rep(i,1,n+1) pp[i]=mul(pp[i-1],x[i]);
	rep(i,1,n+1) a[i]=x[i],b[i]=y[i];
	build(1,1,n);
	return nd[1].f;
}

void updateX(int pos,int val) {
	assert(false);
}

void updateY(int pos,int val) {
	assert(false);
}

Compilation message (stderr)

horses.cpp: In function 'int rnd(int)':
horses.cpp:18:33: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   18 | int rnd(int x) { return mrand() % x;}
      |                         ~~~~~~~~^~~
horses.cpp: In function 'void build(int, int, int)':
horses.cpp:58:16: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} may change value [-Wconversion]
   58 |   nd[p].mx=ps[l]+log10(b[l]);
      |            ~~~~^
horses.cpp:62:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |  int md=l+r>>1;
      |         ~^~
horses.cpp: In function 'void modify(int, int, int, int, int, db, ll)':
horses.cpp:77:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |  int md=l+r>>1;
      |         ~^~
horses.cpp: In function 'll init(int, int*, int*)':
horses.cpp:85:27: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} may change value [-Wconversion]
   85 |  rep(i,1,n+1) ps[i]=ps[i-1]+log10(x[i]);
      |                     ~~~~~~^
horses.cpp:85:28: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'll' {aka 'long long int'} may change value [-Wfloat-conversion]
   85 |  rep(i,1,n+1) ps[i]=ps[i-1]+log10(x[i]);
      |                     ~~~~~~~^~~~~~~~~~~~
horses.cpp: In function 'void updateX(int, int)':
horses.cpp:92:18: warning: unused parameter 'pos' [-Wunused-parameter]
   92 | void updateX(int pos,int val) {
      |              ~~~~^~~
horses.cpp:92:26: warning: unused parameter 'val' [-Wunused-parameter]
   92 | void updateX(int pos,int val) {
      |                      ~~~~^~~
horses.cpp: In function 'void updateY(int, int)':
horses.cpp:96:18: warning: unused parameter 'pos' [-Wunused-parameter]
   96 | void updateY(int pos,int val) {
      |              ~~~~^~~
horses.cpp:96:26: warning: unused parameter 'val' [-Wunused-parameter]
   96 | void updateY(int pos,int val) {
      |                      ~~~~^~~

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