Submission #115614

#	Time	Username	Problem	Language	Result	Execution time	Memory
115614		E869120	Horses (IOI15_horses)	C++14	100 / 100	843 ms	64700 KiB

horses

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

const long long mod = 1000000007;

class RangeMax {
	public:
	vector<long long> dat; int size_ = 1;
	
	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, 0);
	}
	void update(int pos, int x) {
		pos += size_; dat[pos] = x;
		while (pos >= 2) {
			pos >>= 1;
			dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
		}
	}
	long long query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u];
		if (r <= a || b <= l) return 0LL;
		long long s1 = query_(l, r, a, (a + b) >> 1, u * 2);
		long long s2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return max(s1, s2);
	}
	long long query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 30; i++) {
		if ((b & (1LL << i)) != 0) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long INV(long long x) {
	return modpow(x, mod - 2, mod);
}

set<pair<int, long long>>S; RangeMax Z;
long long NN, A[500009], B[500009], TotalSum = 1;

long long calculate() {
	auto itr = S.end(); long long L = 1; vector<pair<long long, long long>> vec;
	while (itr != S.begin()) {
		itr--;
		pair<int, long long> E = (*itr);
		long long D = Z.query(1LL * E.first, NN + 1);
		//cout << "[" << E.first << ", " << NN + 1 << "] = " << D << endl;
		vec.push_back(make_pair(D, L));
		
		L *= E.second; if (L > (1LL << 30)) break;
	}
	if (L <= (1LL << 30)) vec.push_back(make_pair(Z.query(0, NN + 1), L));
	
	/*cout << "vec : " << endl;
	for (int i = 0; i < vec.size(); i++) cout << vec[i].first << " / " << vec[i].second << endl;
	cout << endl;*/
	
	long long maxn = 0;
	for (int i = 0; i < (int)vec.size(); i++) {
		maxn = max(maxn, 1LL * vec[i].first * (vec[vec.size() - 1].second / vec[i].second));
	}
	maxn %= mod;
	
	long long s1 = TotalSum;
	if ((int)vec.size() >= 1) { s1 *= INV(vec[vec.size() - 1].second); s1 %= mod; }
	
	return maxn * s1 % mod;
}

int init(int N, int X[], int Y[]) {
	NN = N; Z.init(NN + 2);
	for (int i = 0; i < N; i++) { A[i] = X[i]; B[i] = Y[i]; }
	for (int i = 0; i < N; i++) {
		Z.update(i, B[i]); TotalSum *= (1LL * A[i]); TotalSum %= mod;
		if (A[i] != 1) S.insert(make_pair(i, A[i]));
	}
	return calculate();
}

int updateX(int i, int val) {
	TotalSum *= INV(A[i]); TotalSum %= mod; if (A[i] != 1) S.erase(make_pair(i, A[i]));
	A[i] = val;
	TotalSum *= A[i]; TotalSum %= mod; if (A[i] != 1) S.insert(make_pair(i, A[i]));
	return calculate();
}

int updateY(int pos, int val) {
	Z.update(pos, val);
	return calculate();
}

Compilation message (stderr)

horses.cpp: In function 'long long int calculate()':
horses.cpp:55:43: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   long long D = Z.query(1LL * E.first, NN + 1);
                                        ~~~^~~
horses.cpp:61:62: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  if (L <= (1LL << 30)) vec.push_back(make_pair(Z.query(0, NN + 1), L));
                                                           ~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:80:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  NN = N; Z.init(NN + 2);
                 ~~~^~~
horses.cpp:83:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   Z.update(i, B[i]); TotalSum *= (1LL * A[i]); TotalSum %= mod;
               ~~~^
horses.cpp:86:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return calculate();
         ~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:93:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return calculate();
         ~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:98:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return calculate();
         ~~~~~~~~~^~

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