Submission #1090474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090474		owoovo	Horses (IOI15_horses)	C++17	34 / 100	333 ms	53452 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[100010],y[100010],n;
struct BIT{
	ll ori[100010];
	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[400010];
	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;
			push(l,m,lc);
			push(m+1,r,rc);
			pull(l,r,id);
		}
		ori[id].tag=0;
		return;
	}
	void build(int l,int r,int id){
		ori[id].val={0,l};
		ori[id].tag=0;
		if(l==r){
			return;
		}
		int m=(l+r)>>1;
		build(l,m,lc);
		build(m+1,r,rc);
		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;
		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);
		}
		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();
	seg.build(1,n,0);
	for(int i=1;i<=n;i++){
		seg.modify(1,n,i,n,0,log2l(x[i]));
		seg.modify(1,n,i,i,0,log2l(y[i]));
		bit.modify(x[i],i);
	}
	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),pos);
	bit.modify(val,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:26:17: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   26 |  void modify(ll x,int pos){
      |                 ^
horses.cpp:19:4: note: shadowed declaration is here
   19 | ll x[100010],y[100010],n;
      |    ^
horses.cpp: In member function 'void SEG_TREE::modify(int, int, int, int, int, long double)':
horses.cpp:81:50: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   81 |  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[100010],y[100010],n;
      |    ^
horses.cpp: In function 'long long int q()':
horses.cpp:116:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  116 |  pair<ld,int> ans=seg.query(1,n,1,n,0);
      |                               ^
horses.cpp:116:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  116 |  pair<ld,int> ans=seg.query(1,n,1,n,0);
      |                                   ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:132:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |  seg.build(1,n,0);
      |              ^
horses.cpp:134:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  134 |   seg.modify(1,n,i,n,0,log2l(x[i]));
      |                ^
horses.cpp:134:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  134 |   seg.modify(1,n,i,n,0,log2l(x[i]));
      |                    ^
horses.cpp:135:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  135 |   seg.modify(1,n,i,i,0,log2l(y[i]));
      |                ^
horses.cpp:138:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |  return q();
      |         ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:143:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  143 |  seg.modify(1,n,pos,n,0,log2l(val)-log2l(x[pos]));
      |               ^
horses.cpp:143:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  143 |  seg.modify(1,n,pos,n,0,log2l(val)-log2l(x[pos]));
      |                     ^
horses.cpp:147:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  147 |  return q();
      |         ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:152:15: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  152 |  seg.modify(1,n,pos,pos,0,log2l(val)-log2l(y[pos]));
      |               ^
horses.cpp:154:10: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  154 |  return q();
      |         ~^~

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