Submission #296566

#	Time	Username	Problem	Language	Result	Execution time	Memory
296566		tmwilliamlin168	Horses (IOI15_horses)	C++14	17 / 100	170 ms	46208 KiB

horses

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

#define ll long long

const int mxN=5e5, M=1e9+7;
int n, sty[2*mxN], cy[mxN];
ll stx[2*mxN];
set<int> s;

ll qryx(int l, int r) {
	ll b=1;
	for(l+=n, r+=n; l<r; ++l/=2, r/=2) {
		if(l&1)
			b=b*sty[l]%M;
		if(r&1)
			b=b*sty[r-1]%M;
	}
	return b;
}

int qryy(int l, int r) {
	int b=0;
	for(l+=n, r+=n; l<r; ++l/=2, r/=2) {
		if(l&1)
			b=max(sty[l], b);
		if(r&1)
			b=max(sty[r-1], b);
	}
	return b;
}

int c() {
	ll mx=0;
	auto it=s.end();
	while(mx<=1e9&&it!=s.begin()) {
		--it;
		mx=max((ll)cy[*it], mx);
		mx*=stx[n+*it];
	}
	return mx%M*qryx(0, *it)%M;
}

int updateX(int i, int x) {
	int j=i+n;
	for(stx[j]=x; j/=2;)
		stx[j]=stx[2*j]*stx[2*j+1]%M;
	auto it=s.upper_bound(i);
	int r=*it, l=*--it;
	cy[l]=qryy(l, r);
	if(l==i) {
		r=*it, l=*--it;
		cy[l]=qryy(l, r);
	}
	return c();
}

int updateY(int i, int x) {
	int j=i+n;
	for(sty[j]=x; j/=2;)
		sty[j]=max(sty[2*j], sty[2*j+1]);
	auto it=s.upper_bound(i);
	int r=*it, l=*--it;
	cy[l]=qryy(l, r);
	return c();
}

int init(int n, int* x, int* y) {
	::n=n;
	for(int i=0; i<n; ++i) {
		stx[n+i]=x[i];
		sty[n+i]=y[i];
		if(!i||x[i]>1)
			s.insert(s.end(), i);
	}
	s.insert(s.end(), n);
	for(int i=n-1; i; --i) {
		stx[i]=stx[2*i]*stx[2*i+1]%M;
		sty[i]=max(sty[2*i], sty[2*i+1]);
	}
	for(auto it=s.begin(); *it<n;) {
		int l=*it, r=*++it;
		cy[l]=qryy(l, r);
	}
	return c();
}

Compilation message (stderr)

horses.cpp: In function 'int c()':
horses.cpp:37:8: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   37 |  while(mx<=1e9&&it!=s.begin()) {
      |        ^~
horses.cpp:42:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   42 |  return mx%M*qryx(0, *it)%M;
      |         ~~~~~~~~~~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:69:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   69 | int init(int n, int* x, int* y) {
      |                               ^
horses.cpp:8:5: note: shadowed declaration is here
    8 | int n, sty[2*mxN], cy[mxN];
      |     ^

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