Submission #1090575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090575		owoovo	Horses (IOI15_horses)	C++17	100 / 100	485 ms	146988 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define F first 
#define S second
#define lc id*2+1
#define rc id*2+2
using namespace std;
const ll p=1e9+7;
ll pw(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1)ans*=a,ans%=p;
		b>>=1,a*=a,a%=p;
	}
	return ans;
}
ll x[500010],y[500010],n;
ld x2[500010],y2[500010],u[500010];
struct BIT{
	ll ori[500010];
	void init(){
		for(int i=0;i<=n;i++)ori[i]=1;
		return;
	}
	void modify(ll x,int pos){
		while(pos<=n){
			ori[pos]*=x;
			ori[pos]%=p;
			pos+=pos&(-pos);
		}
		return;
	}
	ll query(ll pos){
		ll ans=1;
		while(pos){
			ans*=ori[pos];
			ans%=p;
			pos-=pos&(-pos);
		}
		return ans;
	}
}bit;
struct node{
	pair<ld,int> val;
	ld tag;
	node(){
	}
};
struct SEG_TREE{
	node ori[2000010];
	void pull(int l,int r,int id){
		if(l==r)return;
		ori[id].val=max(ori[lc].val,ori[rc].val);
		return;
	}
	void push(int l,int r,int id){
		ori[id].val.F+=ori[id].tag;
		if(l!=r){
			int m=(l+r)>>1;
			ori[lc].tag+=ori[id].tag;
			ori[rc].tag+=ori[id].tag;
		}
		ori[id].tag=0;
		return;
	}
	void build(int l,int r,int id){
		ori[id].tag=0;
		if(l==r){
			ori[id].val={u[l],l};
			return;
		}
		int m=(l+r)>>1;
		build(l,m,lc);
		build(m+1,r,rc);
		pull(l,r,id);
		return;
	}
	void modify(int l,int r,int ml,int mr,int id,ld x){
		push(l,r,id);
		if(l==ml&&r==mr){
			ori[id].tag+=x;
			push(l,r,id);
			return;
		}
		int m=(l+r)>>1;
        push(l,m,lc);
        push(m+1,r,rc);
        pull(l,r,id);
		if(mr<=m){
			modify(l,m,ml,mr,lc,x);
		}else if(m<ml){
			modify(m+1,r,ml,mr,rc,x);
		}else{
			modify(l,m,ml,m,lc,x);
			modify(m+1,r,m+1,mr,rc,x);
		}
        push(l,m,lc);
        push(m+1,r,rc);
        pull(l,r,id);
		return;
	}
	pair<ld,int> query(int l,int r,int ql,int qr,int id){
		push(l,r,id);
		if(l==ql&&r==qr){
			return ori[id].val;
		}
		int m=(l+r)>>1;
		if(qr<=m){
			return query(l,m,ql,qr,lc);
		}else if(m<ql){
			return query(m+1,r,ql,qr,rc);
		}else{
			return max(query(l,m,ql,m,lc),query(m+1,r,m+1,qr,rc));
		}
	}
}seg;
 
ll q(){
	pair<ld,int> ans=seg.query(1,n,1,n,0);
	ll a=bit.query(ans.S);
	a*=y[ans.S];
	a%=p;
	return a;
}
 
 
 
int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=0;i<n;i++){
		x[i+1]=X[i];
		y[i+1]=Y[i];
	}
	bit.init();
	for(int i=1;i<=n;i++){
		x2[i]=log2l(x[i]);
		y2[i]=log2l(y[i]);
		bit.modify(x[i],i);
	}
	ld now=0;
	for(int i=1;i<=n;i++){	
		now+=x2[i];
		u[i]=now+y2[i];
	}
	seg.build(1,n,0);
	return q();
}
 
int updateX(int pos, int val) {	
	pos+=1;
	seg.modify(1,n,pos,n,0,log2l(val)-log2l(x[pos]));
	bit.modify((pw(x[pos],p-2)*val)%p,pos);
	x[pos]=val;
	return q();
}
 
int updateY(int pos, int val) {
	pos+=1;
	seg.modify(1,n,pos,pos,0,log2l(val)-log2l(y[pos]));
	y[pos]=val;
	return q();
}

Compilation message (stderr)

horses.cpp: In member function 'void BIT::modify(long long int, int)':
horses.cpp:27:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   27 |  void modify(ll x,int pos){
      |                 ^
horses.cpp:19:4: note: shadowed declaration is here
   19 | ll x[500010],y[500010],n;
      |    ^
horses.cpp: In member function 'void SEG_TREE::push(int, int, int)':
horses.cpp:61:8: warning: unused variable 'm' [-Wunused-variable]
   61 |    int m=(l+r)>>1;
      |        ^
horses.cpp: In member function 'void SEG_TREE::modify(int, int, int, int, int, long double)':
horses.cpp:80:50: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   80 |  void modify(int l,int r,int ml,int mr,int id,ld x){
      |                                                  ^
horses.cpp:19:4: note: shadowed declaration is here
   19 | ll x[500010],y[500010],n;
      |    ^
horses.cpp: In function 'long long int q()':
horses.cpp:121:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |  pair<ld,int> ans=seg.query(1,n,1,n,0);
      |                               ^
horses.cpp:121:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |  pair<ld,int> ans=seg.query(1,n,1,n,0);
      |                                   ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:147:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  147 |  seg.build(1,n,0);
      |              ^
horses.cpp:148:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  148 |  return q();
      |         ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:153:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  153 |  seg.modify(1,n,pos,n,0,log2l(val)-log2l(x[pos]));
      |               ^
horses.cpp:153:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  153 |  seg.modify(1,n,pos,n,0,log2l(val)-log2l(x[pos]));
      |                     ^
horses.cpp:156:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  156 |  return q();
      |         ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:161:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  161 |  seg.modify(1,n,pos,pos,0,log2l(val)-log2l(y[pos]));
      |               ^
horses.cpp:163:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  163 |  return q();
      |         ~^~

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