Submission #791193

#	Time	Username	Problem	Language	Result	Execution time	Memory
791193		shoryu386	Horses (IOI15_horses)	C++17	100 / 100	698 ms	170412 KiB

horses

#include <bits/stdc++.h>
using namespace std;
//#include "horses.h"
#define ll long long
#define MOD 1000000007

set<ll> multiIndices;
int mainX[500007], mainY[500007];
struct node{
	ll mx;
	ll product;
	ll s, e, m;
	node *l, *r;
	
	node(int x, int y, bool readFromX){
		s = x, e = y; m = (s+e)/2; 
		
		if (s != e){
			l = new node(x, m, readFromX);
			r = new node(m+1, y, readFromX);
		}
		else if (readFromX){
			product = mainX[s];
			mx = mainX[s];
			return;
		}
		else {
			product = mainY[s];
			mx = mainY[s];
			return;
		}
		
		mx = max(l->mx, r->mx);
		product = (l->product * r->product)%MOD;
	}
	
	void update(int idx, ll val){
		if (s == e){
			product = val;
			mx = val;
			return;
		}
		else if (idx <= m) l->update(idx, val);
		else r->update(idx, val);
		
		mx = max(l->mx, r->mx);
		product = (l->product * r->product)%MOD;
	}
	
	ll productQuery(int x, int y){
		if (x <= s && y >= e){
			return product; //entirely contained
		}
		
		if (y <= m){
			return l->productQuery(x, y);
		}
		
		if (x >= m+1){
			return r->productQuery(x, y);
		}
		
		return (l->productQuery(x, m) * r->productQuery(m+1, y))%MOD;
	}
	
	ll maxQuery(int x, int y){
		if (x <= s && y >= e){
			return mx; //entirely contained
		}
		
		if (y <= m){
			return l->maxQuery(x, y);
		}
		
		if (x >= m+1){
			return r->maxQuery(x, y);
		}
		
		return max(l->maxQuery(x, m), r->maxQuery(m+1, y));
	}
};

int n;

node *repro;
node *sellPrice;

ll calc(){
	vector<int> indices;
	auto iter = multiIndices.rbegin();
	for (int x = 0; x < 32; x++){
		if (iter == multiIndices.rend()) break;
		indices.push_back(*iter);
		iter++;
	}
	if (indices.size() == 0 || indices.back() != 0) indices.push_back(0);
	reverse(indices.begin(), indices.end());
	
	indices.push_back(n);
	
	//cout << "\n";
	//for (int i : indices) cout << i << ' ';
	//cout << "\n";
	ll ansLoc = 0;
	ll ans = (sellPrice->maxQuery(0, indices[1] - 1) * repro->productQuery(0, 0))%MOD;
	ll multiplier = 1;
	for (int x = 1; x < indices.size() - 1; x++){
		//cout << repro->productQuery(0, indices[x]) << ' ' << sellPrice->maxQuery(indices[x], indices[x+1] - 1) << "\n\n\n";
		multiplier *= repro->productQuery(indices[x], indices[x]);
		ll sp = sellPrice->maxQuery(indices[x], indices[x+1] - 1);
		if (multiplier >= 1000000000 || ans <= multiplier * sp){
			ans = sp; multiplier = 1; ansLoc = x;
		} 
		
		//ans = max(ans, (repro->productQuery(0, indices[x]) * sellPrice->maxQuery(indices[x], indices[x+1] - 1))%MOD);
		//oh this is wrong lmaooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
	}
	
	return (repro->productQuery(0, indices[ansLoc]) * sellPrice->maxQuery(indices[ansLoc], indices[ansLoc+1] - 1))%MOD;
}

int updateX(int pos, int val) {
	if (mainX[pos] > 1) multiIndices.erase(multiIndices.find(pos));	
	mainX[pos] = val;
	repro->update(pos, val);
	if (mainX[pos] > 1) multiIndices.insert(pos);
	return calc();
}

int updateY(int pos, int val) {
	mainY[pos] = val;
	sellPrice->update(pos, val);
	return calc();
}

int init(int N, int X[], int Y[]) {
	n = N;

	

	for (int x = 0; x < N; x++) { mainX[x] = X[x]; if (X[x] > 1) multiIndices.insert(x);}
	for (int x = 0; x < N-1; x++) { mainY[x] = Y[x];}
	repro = new node(0, N, 1);
	sellPrice = new node(0, N, 0);
	return updateY(N-1, Y[N-1]);
}

Compilation message (stderr)

horses.cpp: In constructor 'node::node(int, int, bool)':
horses.cpp:19:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |    l = new node(x, m, readFromX);
      |                    ^
horses.cpp:20:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   20 |    r = new node(m+1, y, readFromX);
      |                 ~^~
horses.cpp: In member function 'long long int node::productQuery(int, int)':
horses.cpp:63:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |   return (l->productQuery(x, m) * r->productQuery(m+1, y))%MOD;
      |                              ^
horses.cpp:63:52: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   63 |   return (l->productQuery(x, m) * r->productQuery(m+1, y))%MOD;
      |                                                   ~^~
horses.cpp: In member function 'long long int node::maxQuery(int, int)':
horses.cpp:79:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |   return max(l->maxQuery(x, m), r->maxQuery(m+1, y));
      |                             ^
horses.cpp:79:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |   return max(l->maxQuery(x, m), r->maxQuery(m+1, y));
      |                                             ~^~
horses.cpp: In function 'long long int calc()':
horses.cpp:93:21: warning: conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   93 |   indices.push_back(*iter);
      |                     ^~~~~
horses.cpp:107:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (int x = 1; x < indices.size() - 1; x++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:127:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |  return calc();
      |         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:133:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |  return calc();
      |         ~~~~^~

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