Submission #160537

#	Time	Username	Problem	Language	Result	Execution time	Memory
160537		FiloSanza	Horses (IOI15_horses)	C++14	100 / 100	1251 ms	40524 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 1e9+7;

vector<pair<long long, bool>> segX;
vector<int> segY;
vector<int> Y;
int S;

inline int left(int i){return i*2+1;}
inline int right(int i){return (i+1)*2;}
inline int father(int i){return (i-1)/2;}

pair<long long, bool> mergeX(pair<long long, bool> a, pair<long long, bool> b){
	long long val = (a.first * b.first); 
	bool o = val >= MOD || a.second || b.second;
	return {val % MOD, o};
}

pair<long long, bool> queryX(int pos, int l, int h, int a, int b){
	if(h < a || l > b) return {1, false};
	if(l >= a && b >= h) return segX[pos];
	int mid = (l+h)/2;
	return mergeX(queryX(left(pos), l, mid, a, b), queryX(right(pos), mid+1, h, a, b));
}

int mergeY(int a, int b){
	auto query = queryX(0, 0, S/2, a+1, b);
	if(query.second) return b;
	return Y[a] < 1LL * query.first * Y[b] ? b : a;
}

int init(int N, int X[], int Y[]) {
	S = (1 << (int)ceil(log2(N) + 1)) - 1;
	segX.resize(S, {1, false});
	segY.resize(S, N);
	::Y.resize(N);
	for(int i=0; i<N; i++) ::Y[i] = Y[i];
	::Y.push_back(0);
	iota(segY.begin()+S/2, segY.begin()+S/2+N, 0);

	for(int i=0; i<N; i++) segX[i+S/2] = {X[i], false};

	for(int i=S/2-1; i>=0; i--){
		segX[i] = mergeX(segX[left(i)], segX[right(i)]);
		segY[i] = mergeY(segY[left(i)], segY[right(i)]);
	}

	return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}

int updateX(int i, int val) {	
	i += S/2;
	segX[i].first = val;
	while(i != 0){
		i = father(i);
		segX[i] = mergeX(segX[left(i)], segX[right(i)]);
		segY[i] = mergeY(segY[left(i)], segY[right(i)]);
	}

	return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}

int updateY(int i, int val) {
	Y[i] = val;
	i += S/2;
	while(i != 0){
		i = father(i);
		segX[i] = mergeX(segX[left(i)], segX[right(i)]);
		segY[i] = mergeY(segY[left(i)], segY[right(i)]);
	}

	return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:36:33: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:10:13: note: shadowed declaration is here
 vector<int> Y;
             ^
horses.cpp:52:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:64:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:76:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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