Submission #395787

#	Time	Username	Problem	Language	Result	Execution time	Memory
395787		peuch	Horses (IOI15_horses)	C++17	17 / 100	584 ms	50244 KiB

horses

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

const long long MAXN = 5e5 + 10;
const long long MOD = 1e9 + 7;

long long n;
long long x[MAXN], y[MAXN];

long long segX[4 * MAXN], segY[4 * MAXN], segV[4 * MAXN];

long long merge(long long pos, long long e, long long d);
void buildY(long long pos, long long ini, long long fim);
void buildX(long long pos, long long ini, long long fim);
void buildV(long long pos, long long ini, long long fim);
long long queryX(long long pos, long long ini, long long fim, long long p, long long q);
long long queryV(long long pos, long long ini, long long fim, long long p, long long q);
void upY(long long pos, long long ini, long long fim, long long id);
void upX(long long pos, long long ini, long long fim, long long id);
void upV(long long pos, long long ini, long long fim, long long id);

int init(int N, int X[], int Y[]) {
	n = N;
	for(long long i = 1; i <= n; i++)
		x[i] = X[i - 1], y[i] = Y[i - 1];
	buildX(1, 1, n);
	buildV(1, 1, n);
	buildY(1, 1, n);
	return (y[segY[1]] * queryV(1, 1, n, 1, segY[1])) % MOD;
}

long long merge(long long e, long long d){
	long long aux = queryX(1, 1, n, e + 1, d);
	if(aux * y[d] >= y[e]) return d;
	else return e;
}

void buildY(long long pos, long long ini, long long fim){
	if(ini == fim){
		segY[pos] = ini;
		return;
	}
	long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	buildY(e, ini, mid);
	buildY(d, mid + 1, fim);
	segY[pos] = merge(segY[e], segY[d]);
}

void buildX(long long pos, long long ini, long long fim){
	if(ini == fim){
		segX[pos] = x[ini];
		return;
	}
	long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	buildX(e, ini, mid);
	buildX(d, mid + 1, fim);
	segX[pos] = min(MOD + 1, segX[e] * segX[d]);
}

void buildV(long long pos, long long ini, long long fim){
	if(ini == fim){
		segV[pos] = x[ini];
		return;
	}
	long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	buildV(e, ini, mid);
	buildV(d, mid + 1, fim);
	segV[pos] = (segV[e] * segV[d]) % MOD;
}

long long queryX(long long pos, long long ini, long long fim, long long p, long long q){
	if(ini > q || fim < p) return 1;
	if(ini >= p && fim <= q) return segX[pos];
	long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	return min(queryX(e, ini, mid, p, q) * queryX(d, mid + 1, fim, p, q), MOD + 1);
}

long long queryV(long long pos, long long ini, long long fim, long long p, long long q){
	if(ini > q || fim < p) return 1;
	if(ini >= p && fim <= q) return segV[pos];
	long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	return (queryV(e, ini, mid, p, q) * queryV(d, mid + 1, fim, p, q)) % MOD;
}

void upY(long long pos, long long ini, long long fim, long long id){
	if(ini > id || fim < id) return;
	if(ini == fim) return;
	long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	upY(e, ini, mid, id);
	upY(d, mid + 1, fim, id);
	segY[pos] = merge(segY[e], segY[d]);
}

void upX(long long pos, long long ini, long long fim, long long id){
	if(ini > id || fim < id) return;
	if(ini == fim) {segX[pos] = x[id]; return;}
	long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	upX(e, ini, mid, id);
	upX(d, mid + 1, fim, id);
	segX[pos] = min(MOD + 1, segX[e] * segX[d]);
}

void upV(long long pos, long long ini, long long fim, long long id){
	if(ini > id || fim < id) return;
	if(ini == fim) {segV[pos] = x[id]; return;}
	long long mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	upV(e, ini, mid, id);
	upV(d, mid + 1, fim, id);
	segV[pos] = (segV[e] * segV[d]) % MOD;
}

int updateY(int pos, int val){
	pos++;
	y[pos] = val;
	upY(1, 1, n, pos);
	return (y[segY[1]] * queryV(1, 1, n, 1, segY[1])) % MOD;
}

int updateX(int pos, int val){
	pos++;
	x[pos] = val;
	upX(1, 1, n, pos);
	upV(1, 1, n, pos);
	return (y[segY[1]] * queryV(1, 1, n, 1, segY[1])) % MOD;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:30:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   30 |  return (y[segY[1]] * queryV(1, 1, n, 1, segY[1])) % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:117:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  117 |  return (y[segY[1]] * queryV(1, 1, n, 1, segY[1])) % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:125:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  125 |  return (y[segY[1]] * queryV(1, 1, n, 1, segY[1])) % MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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