Submission #341222

#	Time	Username	Problem	Language	Result	Execution time	Memory
341222		Kerim	말 (IOI15_horses)	C++17	100 / 100	371 ms	83564 KiB

horses

#include "horses.h"
#include "bits/stdc++.h"
#define MAXN 500009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<long double,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
PII a[MAXN],b[MAXN],s[MAXN<<2];
double par[MAXN],lazy[MAXN<<2];
int F[MAXN],n;
int mod(ll x){
	return (x%INF);
}
void build(int nd,int x,int y){
	if(x==y){
		s[nd]=mp(par[x]+b[x].ff,x);
		return;
	}
	int mid=(x+y)>>1;
	build(nd<<1,x,mid);
	build(nd<<1|1,mid+1,y);
	s[nd]=max(s[nd<<1],s[nd<<1|1]);
}
void upd(int x,int val){
	for(;x<=n;x+=x&(-x))
		F[x]=mod(F[x]*1LL*val);	
}
void shift(int nd){
	double &ret=lazy[nd];
	lazy[nd<<1]+=ret;s[nd<<1].ff+=ret;
	lazy[nd<<1|1]+=ret;s[nd<<1|1].ff+=ret;	
	ret=0;
}
void inc(int l,int r,double v,int nd,int x,int y){
	if(l>y or x>r)
		return;
	if(l<=x and y<=r){
		s[nd].ff+=v;
		lazy[nd]+=v;
		return;	
	}
	shift(nd);
	int mid=(x+y)>>1;
	inc(l,r,v,nd<<1,x,mid);
	inc(l,r,v,nd<<1|1,mid+1,y);
	s[nd]=max(s[nd<<1],s[nd<<1|1]);
}
int get(){
	int x=s[1].ss;
	int res=b[x].ss;
	for(;x;x-=x&(-x))res=mod(res*1LL*F[x]);
	return res;
}
int init(int N, int X[], int Y[]) {n=N;
	for(int i=1;i<=n;i++)
		b[i]=mp(log(Y[i-1]),Y[i-1]),a[i]=mp(log(X[i-1]),X[i-1]),par[i]=(a[i].ff+par[i-1]),F[i]=1;
	for(int i=1;i<=n;i++)upd(i,a[i].ss);
	build(1,1,n);
	return get();
}
int Fe(int x,int y){
	if(!y)return 1;
	int h=Fe(x,y/2);
	h=mod(h*1LL*h);
	if(y&1)h=mod(h*1LL*x);
	return h;	
}
int updateX(int pos, int val) {	
	inc(pos+1,n,log(val)-a[pos+1].ff,1,1,n);
	upd(pos+1,mod(val*1LL*Fe(a[pos+1].ss,INF-2)));
	a[pos+1]=mp(log(val),val);
	return get();
}

int updateY(int pos, int val) {
	inc(pos+1,pos+1,log(val)-b[pos+1].ff,1,1,n);
	b[pos+1]=mp(log(val),val);
	return get();
}

Compilation message (stderr)

horses.cpp: In function 'int mod(ll)':
horses.cpp:25:11: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   25 |  return (x%INF);
      |         ~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:69:74: warning: conversion from 'long double' to 'double' may change value [-Wfloat-conversion]
   69 |   b[i]=mp(log(Y[i-1]),Y[i-1]),a[i]=mp(log(X[i-1]),X[i-1]),par[i]=(a[i].ff+par[i-1]),F[i]=1;
      |                                                                  ~~~~~~~~^~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:82:22: warning: conversion from 'long double' to 'double' may change value [-Wfloat-conversion]
   82 |  inc(pos+1,n,log(val)-a[pos+1].ff,1,1,n);
      |                      ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:89:26: warning: conversion from 'long double' to 'double' may change value [-Wfloat-conversion]
   89 |  inc(pos+1,pos+1,log(val)-b[pos+1].ff,1,1,n);
      |                          ^

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