Submission #1018629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018629		amirhoseinfar1385	Horses (IOI15_horses)	C++17	57 / 100	1555 ms	98436 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10,mod=1e9+7,lg=20,kaf=(1<<(lg));
int allx[maxn],ally[maxn],n;
set<int>st;
struct segment{
	struct node{
		long long maxa,zarb;
		node(){
			maxa=0;
			zarb=1;
		}
	};
	node seg[(1<<(lg+1))];
	void upd(int i,int w){
		i+=kaf;
		seg[i].zarb=seg[i].maxa=w;
		i>>=1;
		while(i>0){
			seg[i].maxa=max(seg[(i<<1)].maxa,seg[(i<<1)^1].maxa);
			seg[i].zarb=seg[(i<<1)].zarb*seg[(i<<1)^1].zarb%mod;
			i>>=1;
		}
	}
	long long porszarb(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 1;
		}
		if(l>=tl&&r<=tr){
			return seg[i].zarb;
		}
		int m=(l+r)>>1;
		return porszarb((i<<1),l,m,tl,tr)*porszarb((i<<1)^1,m+1,r,tl,tr)%mod;
	}
	long long porsmx(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i].maxa;
		}
		int m=(l+r)>>1;
		return max(porsmx((i<<1),l,m,tl,tr),porsmx((i<<1)^1,m+1,r,tl,tr));
	}
}segx,segy;
int calc(){
	long long low=0;
	long long unnow=1;
	vector<int>ind;
	while((int)st.size()>0){
		unnow*=allx[(*st.rbegin())];
		ind.push_back((*st.rbegin()));
		st.erase((*st.rbegin()));
		if(unnow>1000000000){
			break;
		}
	}
	unnow/=allx[ind.back()];
	long long mx=0;
	for(int i=0;i<(int)ind.size();i++){
		mx=max(mx,unnow*segy.porsmx(1,0,kaf-1,ind[i],n));
		unnow/=allx[ind[i]];
	}
	mx%=mod;
	mx*=segx.porszarb(1,0,kaf-1,0,ind.back());
	mx%=mod;
	for(auto x:ind){
		st.insert(x);
	}
	return mx;
}

int init(int N, int X[], int Y[]) {
	n=N;
	allx[0]=1;
	st.insert(0);
	for(int i=1;i<=n;i++){
		//cout<<i<<endl;
		allx[i]=X[i-1];
		segx.upd(i,allx[i]);
		ally[i]=Y[i-1];
		segy.upd(i,ally[i]);
		if(allx[i]>1){
			st.insert(i);
		}
	}
	return calc();
}

int updateX(int pos, int val) {
	pos++;	
	allx[pos]=val;
	if(allx[pos]==1){
		st.erase(pos);
	}else{
		st.insert(pos);
	}
	segx.upd(pos,val);
	return calc();
}

int updateY(int pos, int val) {
	pos++;
	ally[pos]=val;
	segy.upd(pos,val);
	return calc();
}

Compilation message (stderr)

horses.cpp: In function 'int calc()':
horses.cpp:71:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |  return mx;
      |         ^~
horses.cpp:48:12: warning: unused variable 'low' [-Wunused-variable]
   48 |  long long low=0;
      |            ^~~

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