Submission #590788

#	Time	Username	Problem	Language	Result	Execution time	Memory
590788		FatihSolak	Horses (IOI15_horses)	C++17	57 / 100	1588 ms	48368 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define N 500005
using namespace std;
const int mod = 1e9 + 7;
struct node{
	int maxi;
	int prod = 1;
	node(int a,int b){
		maxi = a;
		prod = b;
	}
};
node merge(node a,node b){
	a.prod = (long long)a.prod * b.prod %mod;
	a.maxi = max(a.maxi,b.maxi);
	return a;
}
struct SegTree{
	vector<node> t;
	int n;
	void init(int size){
		n = size;
		t.assign(4*n,node(0,1));
	}
	void upd1(int v,int tl,int tr,int pos,int val){
		if(tl == tr){
			t[v].prod = val;
			return;
		}
		int tm = (tl + tr)/2;
		if(pos <= tm){
			upd1(v*2,tl,tm,pos,val);
		}
		else upd1(v*2+1,tm+1,tr,pos,val);
		t[v] = merge(t[v*2],t[v*2+1]);
	}
	void upd2(int v,int tl,int tr,int pos,int val){
		if(tl == tr){
			t[v].maxi = val;
			return;
		}
		int tm = (tl + tr)/2;
		if(pos <= tm){
			upd2(v*2,tl,tm,pos,val);
		}
		else upd2(v*2+1,tm+1,tr,pos,val);
		t[v] = merge(t[v*2],t[v*2+1]);
	}
	node get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl){
			return node(0,1);
		}
		if(l <= tl && tr <= r){
			return t[v];
		}
		int tm = (tl + tr)/2;
		return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	}
	void upd1(int pos,int val){
		upd1(1,0,n-1,pos,val);
	}
	void upd2(int pos,int val){
		upd2(1,0,n-1,pos,val);
	}
	node get(int l,int r){
		return get(1,0,n-1,l,r);
	}
}tree;
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 = tree.get(l,n-1);
		if(prod * foo.maxi > val){
			val = prod * foo.maxi;
			opt = l;
		}
		if(s.upper_bound(l) == s.end())break;
		l = *s.upper_bound(l);
	}
	return (long long)tree.get(opt,n-1).maxi * tree.get(0,opt).prod % mod;
}
int init(int n_, int X[], int Y[]) {
	n = n_;
	tree.init(n);
	for(int i = 0;i<n;i++){
		x[i] = X[i];
		y[i] = Y[i];
		tree.upd1(i,x[i]);
		tree.upd2(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;
	tree.upd1(pos,x[pos]);
	if(x[pos] > 1){
		s.insert(pos);
	}
	return get_ans();
}

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

Compilation message (stderr)

horses.cpp: In function 'node merge(node, node)':
horses.cpp:15:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 |  a.prod = (long long)a.prod * b.prod %mod;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int get_ans()':
horses.cpp:104:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |  return (long long)tree.get(opt,n-1).maxi * tree.get(0,opt).prod % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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