Submission #104911

#	Time	Username	Problem	Language	Result	Execution time	Memory
104911		arman_ferdous	Horses (IOI15_horses)	C++17	17 / 100	194 ms	65828 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 5e5+10;
const int MOD = 1e9+7;

int n; ll mulz[N];
double X[N], Y[N];
double tmp[N];

struct SGT1{
	struct node{
		int idx;
		double mx, lazy;
	}t[N<<2];

	void build(int node, int L, int R) {
		t[node].lazy = 0;
		if(L == R) {
			t[node].mx = tmp[L];
			t[node].idx = L;
			return;
		} int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		build(lc, L, mid); build(rc, mid+1, R);

		if(t[lc].mx > t[rc].mx) {
			t[node].mx = t[lc].mx;
			t[node].idx = t[lc].idx;
		} else {
			t[node].mx = t[rc].mx;
			t[node].idx = t[rc].idx;
		}
	}
	void shift(int node, int L, int R) {
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		t[lc].mx += t[node].lazy;
		t[rc].mx += t[node].lazy;
		t[node].lazy = 0;

		if(t[lc].mx > t[rc].mx) {
			t[node].mx = t[lc].mx;
			t[node].idx = t[lc].idx;
		} else {
			t[node].mx = t[rc].mx;
			t[node].idx = t[rc].idx;
		}
	}

	void upd(int node, int L, int R, int l, int r, double v) {
		if(r < L || R < l) return;
		if(l <= L && R <= r) {
			t[node].lazy += v;
			t[node].mx += v;
			return;
		} if(t[node].lazy != 0) shift(node, L, R);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		upd(lc, L, mid, l, r, v);
		upd(rc, mid+1, R, l, r, v);
		if(t[lc].mx > t[rc].mx) {
			t[node].mx = t[lc].mx;
			t[node].idx = t[lc].idx;
		} else {
			t[node].mx = t[rc].mx;
			t[node].idx = t[rc].idx;
		}
	}
	int get() { return t[1].idx; }
}opt;

struct SGT2{
	ll t[N<<2], lazy[N<<2];
	void build(int node, int L, int R) {
		lazy[node] = 1;
		if(L == R) return void(t[node] = mulz[L]);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		build(lc, L, mid); build(rc, mid+1, R);
		t[node] = t[lc] * t[rc] % MOD;
	}
	void shift(int node, int L, int R) {
		int lc = node<<1, rc = lc|1;
		t[lc] = t[lc] * lazy[node] % MOD;
		t[rc] = t[rc] * lazy[node] % MOD;
		lazy[node] = 1;
	}
	void upd(int node, int L, int R, int l, int r, ll v) {
		if(r < L || R < l) return;
		if(l <= L && R <= r) {
			t[node] = t[node] * v % MOD;
			lazy[node] = lazy[node] * v % MOD;
			return;
		} if(lazy[node] != 1) shift(node, L, R);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		upd(lc, L, mid, l, r, v); upd(rc, mid+1, R, l, r, v);
		t[node] = t[lc] * t[rc] % MOD;
	}	
	ll get(int node, int L, int R, int pos) {
		if(L == R) return t[node];
		if(lazy[node] != 1) shift(node, L, R);
		int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
		if(pos <= mid) return get(lc, L, mid, pos);
		return get(rc, mid+1, R, pos);
	}
}mul;

int init(int _N, int _X[], int _Y[]) {
	n = _N;
	for(int i = 1; i <= n; i++) X[i] = _X[i-1], Y[i] = _Y[i-1];

	for(int i = 1; i <= n; i++)
		tmp[i] = tmp[i-1] + log(X[i]);
	for(int i = 1; i <= n; i++)
		tmp[i] += log(Y[i]);

	mulz[0] = 1;
	for(int i = 1; i <= n; i++)
		mulz[i] = mulz[i-1] * (ll)X[i] % MOD; 
	for(int i = 1; i <= n; i++)
		mulz[i] = mulz[i] * (ll)Y[i] % MOD;

	opt.build(1,1,n);
	mul.build(1,1,n);
	int idx = opt.get();
	return mul.get(1,1,n,idx);
}

ll powmod(ll a, ll b) {
	ll r = 1;
	while(b) {
		if(b & 1) r = r * a % MOD;
		a = a * a % MOD;
		b>>=1;
	} return r;
}
ll modinv(ll x) { return powmod(x,MOD-2); }

int updateX(int pos, int val) {
	pos++;
	double del = log((double)val) - log((double)X[pos]);
	opt.upd(1,1,n,pos,n,del);

	ll det = (ll)val * modinv(X[pos]) % MOD;
	mul.upd(1,1,n,pos,n,det);

	X[pos] = val;
	int idx = opt.get();
	return mul.get(1,1,n,idx);
}

int updateY(int pos, int val) {
	pos++;
	double del = log((double)val) - log((double)Y[pos]);
	opt.upd(1,1,n,pos,pos,del);

	ll det = (ll)val * modinv(Y[pos]) % MOD;
	mul.upd(1,1,n,pos,pos,det);

	int idx = opt.get();
	return mul.get(1,1,n,idx);
}

Compilation message (stderr)

horses.cpp: In member function 'void SGT1::build(int, int, int)':
horses.cpp:19:37: warning: declaration of 'node' shadows a member of 'SGT1' [-Wshadow]
  void build(int node, int L, int R) {
                                     ^
horses.cpp:14:9: note: shadowed declaration is here
  struct node{
         ^~~~
horses.cpp: In member function 'void SGT1::shift(int, int, int)':
horses.cpp:36:37: warning: declaration of 'node' shadows a member of 'SGT1' [-Wshadow]
  void shift(int node, int L, int R) {
                                     ^
horses.cpp:14:9: note: shadowed declaration is here
  struct node{
         ^~~~
horses.cpp:37:7: warning: unused variable 'mid' [-Wunused-variable]
   int mid = (L+R)>>1, lc = node<<1, rc = lc|1;
       ^~~
horses.cpp: In member function 'void SGT1::upd(int, int, int, int, int, double)':
horses.cpp:51:59: warning: declaration of 'node' shadows a member of 'SGT1' [-Wshadow]
  void upd(int node, int L, int R, int l, int r, double v) {
                                                           ^
horses.cpp:14:9: note: shadowed declaration is here
  struct node{
         ^~~~
horses.cpp: In member function 'void SGT2::shift(int, int, int)':
horses.cpp:81:27: warning: unused parameter 'L' [-Wunused-parameter]
  void shift(int node, int L, int R) {
                           ^
horses.cpp:81:34: warning: unused parameter 'R' [-Wunused-parameter]
  void shift(int node, int L, int R) {
                                  ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:125:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return mul.get(1,1,n,idx);
         ~~~~~~~^~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:143:33: warning: conversion to 'll {aka long long int}' from 'double' may alter its value [-Wfloat-conversion]
  ll det = (ll)val * modinv(X[pos]) % MOD;
                            ~~~~~^
horses.cpp:148:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return mul.get(1,1,n,idx);
         ~~~~~~~^~~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:156:33: warning: conversion to 'll {aka long long int}' from 'double' may alter its value [-Wfloat-conversion]
  ll det = (ll)val * modinv(Y[pos]) % MOD;
                            ~~~~~^
horses.cpp:160:16: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return mul.get(1,1,n,idx);
         ~~~~~~~^~~~~~~~~~~

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