Submission #333413

#	Time	Username	Problem	Language	Result	Execution time	Memory
333413		errorgorn	Horses (IOI15_horses)	C++17	100 / 100	273 ms	103916 KiB

horses

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include "horses.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

const int MOD=1000000007;

ll qexp(ll b,ll p,int m){
	ll res=1;
	while (p){
		if (p&1) res=res*b%m;
		b=b*b%m;
		p>>=1;
	}
	return res;
}

ll inv(ll i){
	return qexp(i,MOD-2,MOD);
}

ll arr[500005];
ll brr[500005];

struct node{
	int s,e,m;
	ll val;
	bool over=false;
	ll num,denom;
	
	node *l,*r;
	
	void mx(ll num2,ll denom2){
		if (num2*denom>num*denom2){
			num=num2;
			denom=denom2;
		}
	}
	
	void init(){
		val=arr[s];
		num=brr[s],denom=1;
	}
	
	void comb(){
		val=l->val*r->val;
		over=l->over|r->over;
		if (val>MOD){
			val%=MOD;
			over=true;
		}
		
		if (!r->over) num=brr[m],denom=r->val;
		else num=0,denom=1;
		
		mx(r->num,r->denom);
		if (!r->over && r->val*l->denom<MOD) mx(l->num,r->val*l->denom);
	}
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			comb();
		}
		else{
			init();
		}
	}
	
	void update(int i){
		if (s==e) {
			init();
			return;
		}
		
		if (i<=m) l->update(i);
		else r->update(i);
		
		comb();
	}
} *root;

int init(int n, int X[], int Y[]) {
	rep(x,0,n) arr[x]=X[x];
	rep(x,0,n) brr[x]=Y[x];
	
	root=new node(0,n-1);
	
	return root->val*root->num%MOD*inv(root->denom)%MOD;
}

int updateX(int pos, int val) {	
	arr[pos]=val;
	root->update(pos);
	
	return root->val*root->num%MOD*inv(root->denom)%MOD;
}

int updateY(int pos, int val) {
	brr[pos]=val;
	root->update(pos);
	
	return root->val*root->num%MOD*inv(root->denom)%MOD;
}

Compilation message (stderr)

horses.cpp: In constructor 'node::node(int, int)':
horses.cpp:82:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:113:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  113 |  return root->val*root->num%MOD*inv(root->denom)%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:120:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |  return root->val*root->num%MOD*inv(root->denom)%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:127:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |  return root->val*root->num%MOD*inv(root->denom)%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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