Submission #669690

#	Time	Username	Problem	Language	Result	Execution time	Memory
669690		victor_gao	Horses (IOI15_horses)	C++17	0 / 100	266 ms	59268 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
#define MAXN 500015
#define mod 1000000007
using namespace std;
int dx[MAXN],dy[MAXN],n;
int fast_pow(int a,int b){
	int ans=1;
	while (b){
		if (b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}

struct segtree{
	ll pos[4*MAXN],val[4*MAXN],val_x[4*MAXN],fac[4*MAXN];
	pii remain[4*MAXN];
	ll get_val(ll a=1,ll b=1,ll c=1,ll d=1){
		vector<ll>vt={a,b,c,d};
		ll ans=1;
		for (ll i:vt){
			ans=ans*i;
			if (ans>1e9) return 1e9+2;
		}
		return ans;
	}
	void pull(int i){
		fac[i]=fac[2*i]*fac[2*i+1]%mod;
		if (get_val(remain[2*i].y,remain[2*i+1].x,val[2*i+1])>val[2*i]){
			pos[i]=pos[2*i+1]; val[i]=val[2*i+1]; remain[i].y=remain[2*i+1].y; val_x[i]=val_x[2*i+1];
			remain[i].x=get_val(remain[2*i].x,remain[2*i].y,val_x[2*i],remain[2*i+1].x);
		}
		else {
			pos[i]=pos[2*i]; val[i]=val[2*i]; remain[i].x=remain[2*i].x; val_x[i]=val_x[2*i];
			remain[i].y=get_val(remain[2*i].y,remain[2*i+1].x,remain[2*i+1].y,val_x[2*i+1]);
		}
	}
	void build(int l,int r,int i){
		if (l==r){
			remain[i]={1,1};
			pos[i]=l; val[i]=dy[l]; fac[i]=dx[l]; val_x[i]=dx[l];
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,2*i);
		build(mid+1,r,2*i+1);
		pull(i);
	}
	void modify_Y(int l,int r,int i,int p,ll c){
		if (l==r){
			val[i]=val[i]*c%mod;
			return;
		}
		int mid=(l+r)>>1;
		if (p<=mid) modify_Y(l,mid,2*i,p,c);
		else modify_Y(mid+1,r,2*i+1,p,c);
		pull(i);
	}
	void modify_X(int l,int r,int i,int p,ll c){
		if (l==r){
			fac[i]=fac[i]*c%mod;
			return;
		}
		int mid=(l+r)>>1;
		if (p<=mid) modify_X(l,mid,2*i,p,c);
		else modify_X(mid+1,r,2*i+1,p,c);
		pull(i);
	}
	ll query(int l,int r,int i,int ql,int qr){
		if (ql<=l&&qr>=r) return fac[i];
		int mid=(l+r)>>1;
		if (qr<=mid) return query(l,mid,2*i,ql,qr);
		else if (ql>mid) return query(mid+1,r,2*i+1,ql,qr);
		else return query(l,mid,2*i,ql,qr)*query(mid+1,r,2*i+1,ql,qr)%mod;
	}
	void debug(int l,int r,int i){
		cout<<l<<" ~ "<<r<<" : "<<fac[i]<<" best "<<pos[i]<<","<<val[i]<<","<<val_x[i]<<" remain : "<<remain[i].x<<' '<<remain[i].y<<'\n';
		if (l==r) return;
		int mid=(l+r)>>1;
		debug(l,mid,2*i);
		debug(mid+1,r,2*i+1);
	}
}seg;
int init(int N, int X[], int Y[]) {
	n=N;
	for (int i=1;i<=n;i++){
		dx[i]=X[i-1]; dy[i]=Y[i-1];
	}
	seg.build(1,n,1);
	int best=seg.pos[1];
	int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
	return ans;
}

int updateX(int pos, int val) {
	pos++;
	int inv=fast_pow(dx[pos],mod-2);	
	dx[pos]=val;
	seg.modify_X(1,n,1,pos,inv);
	seg.modify_X(1,n,1,pos,val);
	int best=seg.pos[1];
	int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
	return ans;
}

int updateY(int pos, int val) {
	pos++;
	int inv=fast_pow(dy[pos],mod-2);
	dy[pos]=val;
	seg.modify_Y(1,n,1,pos,inv);
	seg.modify_Y(1,n,1,pos,val);
	int best=seg.pos[1];
	int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
	return ans;
}

Compilation message (stderr)

horses.cpp: In member function 'long long int segtree::get_val(long long int, long long int, long long int, long long int)':
horses.cpp:29:8: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   29 |    if (ans>1e9) return 1e9+2;
      |        ^~~
horses.cpp: In member function 'void segtree::pull(int)':
horses.cpp:37:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   37 |    remain[i].x=get_val(remain[2*i].x,remain[2*i].y,val_x[2*i],remain[2*i+1].x);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:41:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   41 |    remain[i].y=get_val(remain[2*i].y,remain[2*i+1].x,remain[2*i+1].y,val_x[2*i+1]);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:96:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |  int best=seg.pos[1];
      |           ~~~~~~~~~^
horses.cpp:97:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   97 |  int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
      |                                          ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:107:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  107 |  int best=seg.pos[1];
      |           ~~~~~~~~~^
horses.cpp:108:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  108 |  int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
      |                                          ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:118:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  118 |  int best=seg.pos[1];
      |           ~~~~~~~~~^
horses.cpp:119:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |  int ans=seg.query(1,n,1,1,best)*dy[best]%mod;
      |                                          ^

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