Submission #590793

#	Time	Username	Problem	Language	Result	Execution time	Memory
590793		FatihSolak	Horses (IOI15_horses)	C++17	100 / 100	1287 ms	60804 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define N 500005
using namespace std;
const int mod = 1e9 + 7;
struct SegTree1{
	vector<int> t;
	int n;
	void init(int size){
		n = size;
		t.assign(4*n,0);
	}
	void upd(int v,int tl,int tr,int pos,int val){
		if(tl == tr){
			t[v] = val;
			return;
		}
		int tm = (tl + tr)/2;
		if(pos <= tm){
			upd(v*2,tl,tm,pos,val);
		}
		else upd(v*2+1,tm+1,tr,pos,val);
		t[v] = (long long)t[v*2]*t[v*2+1]%mod;
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl){
			return 1;
		}
		if(l <= tl && tr <= r){
			return t[v];
		}
		int tm = (tl + tr)/2;
		return (long long)get(v*2,tl,tm,l,r)*get(v*2+1,tm+1,tr,l,r)%mod;
	}
	void upd(int pos,int val){
		upd(1,0,n-1,pos,val);
	}
	int get(int l,int r){
		return get(1,0,n-1,l,r);
	}
}tree1;
struct SegTree2{
	vector<int> t;
	int n;
	void init(int size){
		n = size;
		t.assign(4*n,0);
	}
	void upd(int v,int tl,int tr,int pos,int val){
		if(tl == tr){
			t[v] = val;
			return;
		}
		int tm = (tl + tr)/2;
		if(pos <= tm){
			upd(v*2,tl,tm,pos,val);
		}
		else upd(v*2+1,tm+1,tr,pos,val);
		t[v] = max(t[v*2],t[v*2+1]);
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl){
			return 1;
		}
		if(l <= tl && tr <= r){
			return t[v];
		}
		int tm = (tl + tr)/2;
		return max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	}
	void upd(int pos,int val){
		upd(1,0,n-1,pos,val);
	}
	int get(int l,int r){
		return get(1,0,n-1,l,r);
	}
}tree2;
const int BOUND = 1e9;
set<int> s;
int x[N],y[N];
int n;
int get_ans(){
	int l = 0;
	long long prod = 1;
	if(s.size()){
		auto it = prev(s.end());
		while(prod < BOUND){
			prod *= x[*it];
			if(prod >= BOUND){
				l = *it;
			}
			if(it == s.begin())break;
			it = prev(it);
		}
	}
	int tmp = l;
	int opt = l;
	long long val = 0;
	prod = 1;
	while(1){
		if(l != tmp){
			prod *= x[l];
		}
		auto foo = tree2.get(l,n-1);
		if(prod * foo > val){
			val = prod * foo;
			opt = l;
		}
		if(s.upper_bound(l) == s.end())break;
		l = *s.upper_bound(l);
	}
	return (long long)tree2.get(opt,n-1) * tree1.get(0,opt) % mod;
}
int init(int n_, int X[], int Y[]) {
	n = n_;
	tree1.init(n);
	tree2.init(n);
	for(int i = 0;i<n;i++){
		x[i] = X[i];
		y[i] = Y[i];
		tree1.upd(i,x[i]);
		tree2.upd(i,y[i]);
		if(x[i] > 1){
			s.insert(i);
		}
	}
	return get_ans();
}

int updateX(int pos, int val) {	
	if(x[pos] > 1){
		s.erase(pos);
	}
	x[pos] = val;
	tree1.upd(pos,x[pos]);
	if(x[pos] > 1){
		s.insert(pos);
	}
	return get_ans();
}

int updateY(int pos, int val) {
	y[pos] = val;
	tree2.upd(pos,y[pos]);
	return get_ans();
}

Compilation message (stderr)

horses.cpp: In member function 'void SegTree1::upd(int, int, int, int, int)':
horses.cpp:23:36: warning: conversion from 'long long int' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   23 |   t[v] = (long long)t[v*2]*t[v*2+1]%mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In member function 'int SegTree1::get(int, int, int, int, int)':
horses.cpp:33:62: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   33 |   return (long long)get(v*2,tl,tm,l,r)*get(v*2+1,tm+1,tr,l,r)%mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int get_ans()':
horses.cpp:112:58: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |  return (long long)tree2.get(opt,n-1) * tree1.get(0,opt) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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