제출 #669694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
669694		victor_gao	말 (IOI15_horses)	C++17	100 / 100	462 ms	85824 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define x first
#define y second
#define MAXN 500015
#define mod 1000000007
using namespace std;
int dx[MAXN],dy[MAXN],n;
ll fast_pow(ll a,ll b){
	ll 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_x[2*i+1],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;
			val_x[i]=val_x[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);
	ll best=seg.pos[1];
	ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
	return ans;
}

int updateX(int pos, int val) {
	pos++;
	ll 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);
	ll best=seg.pos[1];
	ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
	//cout<<"modify_X "<<best<<" "<<ans<<'\n';
	//seg.debug(1,n,1);
	return ans;
}

int updateY(int pos, int val) {
	pos++;
	ll 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);
	ll best=seg.pos[1];
	ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
	//cout<<"modify_Y "<<best<<" "<<ans<<'\n';
	//seg.debug(1,n,1);
	return ans;
}

컴파일 시 표준 에러 (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 function 'int init(int, int*, int*)':
horses.cpp:98:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |  ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
      |                           ^~~~
horses.cpp:99:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:109:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |  ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
      |                           ^~~~
horses.cpp:112:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:122:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |  ll ans=seg.query(1,n,1,1,best)*dy[best]%mod;
      |                           ^~~~
horses.cpp:125:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  125 |  return ans;
      |         ^~~

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