Submission #1030289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030289		pcc	Horses (IOI15_horses)	C++17	100 / 100	474 ms	55048 KiB

horses

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const ll mod = 1e9+7;
const ll mxn = 5e5+10;

int N;
int arr[mxn],brr[mxn];
set<int> st;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	int mx[mxn*4];
	ll seg[mxn*4];
	void build(int now,int l,int r){
		if(l == r){
			seg[now] = arr[l];
			mx[now] = brr[l];
			return;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		mx[now] = max(mx[ls],mx[rs]);
		seg[now] = seg[ls]*seg[rs];
		if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
		return;
	}
	void modify(int now,int l,int r,int p){
		if(l == r){
			seg[now] = arr[l];
			mx[now] = brr[l];
			return;
		}
		if(mid>=p)modify(ls,l,mid,p);
		else modify(rs,mid+1,r,p);
		mx[now] = max(mx[ls],mx[rs]);
		seg[now] = seg[ls]*seg[rs];
		if(seg[now]>=mod)seg[now] = mod+seg[now]%mod;
	}
	ll getsum(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getsum(ls,l,mid,s,e);
		else if(mid<s)return getsum(rs,mid+1,r,s,e);
		else{
			auto re = getsum(ls,l,mid,s,e)*getsum(rs,mid+1,r,s,e);
			if(re>=mod)return mod+re%mod;
			else return re;
		}
	}
	ll getmax(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return mx[now];
		if(mid>=e)return getmax(ls,l,mid,s,e);
		else if(mid<s)return getmax(rs,mid+1,r,s,e);
		else return max(getmax(ls,l,mid,s,e),getmax(rs,mid+1,r,s,e));
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;

bool cmp(int a,int b){
	if(a>b)return seg.getmax(0,0,N-1,a,N-1)*seg.getsum(0,0,N-1,b+1,a)<seg.getmax(0,0,N-1,b,N-1);
	else return seg.getmax(0,0,N-1,a,N-1)<seg.getmax(0,0,N-1,b,N-1)*seg.getsum(0,0,N-1,a+1,b);
}

ll getans(){
	st.insert(0);
	vector<int> need;
	ll pref = 1;
	for(auto it = st.rbegin();it != st.rend()&&pref<mod;it++){
		need.push_back(*it);
		pref *= arr[*it];
	}
	sort(need.begin(),need.end());
	int tar = need[0];
	for(int i = 1;i<need.size();i++){
		if(cmp(tar,need[i]))tar = need[i];
	}
	return seg.getmax(0,0,N-1,tar,N-1)*seg.getsum(0,0,N-1,0,tar)%mod;
}

int init(int NN, int X[], int Y[]) {
	N = NN;
	for(int i = 0;i<N;i++){
		arr[i] = X[i];
		if(arr[i] != 1)st.insert(i);
		brr[i] = Y[i];
	}
	seg.build(0,0,N-1);
	//cerr<<"INIT! "<<seg.getmax(0,0,N-1,0,N-1)<<endl;
	return getans();
}

int updateX(int pos, int val) {	
	arr[pos] = val;
	if(arr[pos] != 1)st.insert(pos);
	else if(arr[pos] == 1&&st.find(pos) != st.end())st.erase(pos);
	seg.modify(0,0,N-1,pos);
	return getans();
}

int updateY(int pos, int val) {
	brr[pos] = val;
	seg.modify(0,0,N-1,pos);
	return getans();
}

Compilation message (stderr)

horses.cpp: In function 'long long int getans()':
horses.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i = 1;i<need.size();i++){
      |                ~^~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:102:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:110:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  110 |  return getans();
      |         ~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:116:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  116 |  return getans();
      |         ~~~~~~^~

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