Submission #40275

#	Time	Username	Problem	Language	Result	Execution time	Memory
40275		szawinis	Horses (IOI15_horses)	C++14	17 / 100	129 ms	74680 KiB

horses

#include "horses.h"
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
const int N = 1 << 19, MOD = 1e9+7;

ll modPow(ll b, ll e) {
	if(!e) return 1;
	if(e == 1) return b;
	return modPow(b*b % MOD, e >> 1) * modPow(b, e & 1) % MOD;
}

struct node {
	long double comp;
	ll val;
	bool lazy_needed;
	void merge(node rhs) {
		lazy_needed = true;
		comp += rhs.comp;
		val = (val * rhs.val) % MOD;
	}
	bool operator>(const node& rhs) const {
		if(comp > rhs.comp) return true;
		if(val > rhs.val) return true;
		return false;
	}
} t[2*N], lz[2*N];

void build(int i, int l, int r) {
	if(l == r) return;
	int mid = l+r >> 1;
	build(i<<1, l, mid);
	build(i<<1|1, mid+1, r);
	if(t[i<<1] > t[i<<1|1]) t[i] = t[i<<1];
	else t[i] = t[i<<1|1];
}

void apply(int i) {
	t[i].merge(lz[i]);
	if(i < N) {
		lz[i<<1].merge(lz[i]);
		lz[i<<1|1].merge(lz[i]);
	}
	lz[i].lazy_needed = false;
	lz[i].comp = 0, lz[i].val = 1;
}

void update(int i, int l, int r, int tl, int tr, node v) {
	if(lz[i].lazy_needed) apply(i);
	if(l > tr || r < tl) return;
	if(l >= tl && r <= tr) {
		lz[i].merge(v);
		apply(i);
		return;
	}
	int mid = l+r >> 1;
	update(i<<1, l, mid, tl, tr, v);
	update(i<<1|1, mid+1, r, tl, tr, v);
	if(t[i<<1] > t[i<<1|1]) t[i] = t[i<<1];
	else t[i] = t[i<<1|1];
}

int n, x[N], y[N];
int init(int _n, int _x[], int _y[]) {
	n = _n;
	copy(_x, _x+n, x);
	copy(_y, _y+n, y);
	node curr = {0, 1, 0};
	for(int i = 0; i < n; i++) {
		curr.merge((node) {(long double) log2(x[i]), x[i]});
		t[N+i] = curr;
		t[N+i].merge((node) {(long double) log2(y[i]), y[i]});
	}
	build(1, 0, N-1);
	return t[1].val;
}

int updateX(int pos, int val) {	
	long double ncomp = (long double) log2(val) - log2(x[pos]);
	ll nval = 1ll * val * modPow(x[pos], MOD-2) % MOD;
	update(1, 0, N-1, pos, N-1, (node) {ncomp, nval});
	return t[1].val;
}

int updateY(int pos, int val) {
	long double ncomp = (long double) log2(val) - log2(y[pos]);
	ll nval = 1ll * val * modPow(y[pos], MOD-2) % MOD;
	update(1, 0, N-1, pos, pos, (node) {ncomp, nval});
	return t[1].val;
}

Compilation message (stderr)

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:32:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
horses.cpp: In function 'void update(int, int, int, int, int, node)':
horses.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l+r >> 1;
             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:71:52: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
   curr.merge((node) {(long double) log2(x[i]), x[i]});
                                                    ^
horses.cpp:73:54: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
   t[N+i].merge((node) {(long double) log2(y[i]), y[i]});
                                                      ^
horses.cpp:76:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return t[1].val;
              ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:82:49: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
  update(1, 0, N-1, pos, N-1, (node) {ncomp, nval});
                                                 ^
horses.cpp:83:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return t[1].val;
              ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:89:49: warning: missing initializer for member 'node::lazy_needed' [-Wmissing-field-initializers]
  update(1, 0, N-1, pos, pos, (node) {ncomp, nval});
                                                 ^
horses.cpp:90:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return t[1].val;
              ^

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