제출 #121546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121546		nishkarsh	말 (IOI15_horses)	C++14	37 / 100	1170 ms	41164 KiB

horses

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
#define INF 2e9
#define INFLL 4e18
using namespace std;
ll powmod(ll base,ll exponent,ll mod){ // with mod < 1e9
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int upperlimit = 5e5+1;
const int mod = 1e9+7;
struct data
{
	int last_ind=-1,maxy;
	ll mult;
};
data merge(data a,data b){
	data ans;
	ans.mult=a.mult;ans.mult*=b.mult;
	ans.mult%=mod;
	if(b.last_ind==-1) ans.last_ind=a.last_ind;
	else ans.last_ind=b.last_ind;
	ans.maxy=max(a.maxy,b.maxy);
	return ans;
}
data segtree[4*upperlimit];
int n;
ll ans;vi indices;
vi x;vi y;
void build(int node,int i,int j){
	if(i==j){
		segtree[node].mult=x[i];segtree[node].last_ind=i;segtree[node].maxy=y[i];
		if(x[i]==1) segtree[node].last_ind=-1;
		return;
	}
	int mid=(i+j)>>1;
	build(2*node,i,mid);build(2*node+1,mid+1,j);
	segtree[node]=merge(segtree[2*node],segtree[2*node+1]);
}
void update(int node,int i,int j,int ind,int val){
	if(i==j){
		segtree[node].mult=x[i];segtree[node].last_ind=i;segtree[node].maxy=y[i];
		if(x[i]==1) segtree[node].last_ind=-1;
		return;
	}
	int mid=(i+j)>>1;
	if(ind<=mid) update(2*node,i,mid,ind,val);
	else update(2*node+1,mid+1,j,ind,val);
	segtree[node]=merge(segtree[2*node],segtree[2*node+1]);
}
data query(int node,int i,int j,int l,int r){
	if((i>r)||(l>j)||(l>r)||(i>j)){
		data unity;unity.mult=1;unity.maxy=0;unity.last_ind=-1;
		return unity;
	}
	if((i>=l)&&(j<=r)) return segtree[node];
	int mid=(i+j)>>1;
	return merge(query(2*node,i,mid,l,r),query(2*node+1,mid+1,j,l,r));
}
int updateX(int pos,int val){
	x[pos]=val;
	update(1,0,n-1,pos,val);
	int temp=n;
	int ind=n-1;ll calc=y[n-1];
	for(int i = 1; i <= 40; i++){
		indices.pb(query(1,0,n-1,0,temp-1).last_ind);
		temp=indices[indices.size()-1];
		if(temp==-1) break;
		int temp2=query(1,0,n-1,temp,n-1).maxy;
		if(temp2>calc){
			calc=temp2;
			ind=temp;
		}
		calc*=x[temp];
		if(calc>2000000000) break;
	}
	indices.clear();
	ans=query(1,0,n-1,0,ind).mult;ans*=query(1,0,n-1,ind,n-1).maxy;
	ans%=mod;
	return ans;
}
int updateY(int pos,int val){
	y[pos]=val;
	update(1,0,n-1,pos,val);
	int temp=n;
	int ind=n-1;ll calc=y[n-1];
	for(int i = 1; i <= 40; i++){
		indices.pb(query(1,0,n-1,0,temp-1).last_ind);
		temp=indices[indices.size()-1];
		if(temp==-1) break;
		int temp2=query(1,0,n-1,temp,n-1).maxy;
		if(temp2>calc){
			calc=temp2;
			ind=temp;
		}
		calc*=x[temp];
		if(calc>2000000000) break;
	}
	indices.clear();
	ans=query(1,0,n-1,0,ind).mult;ans*=query(1,0,n-1,ind,n-1).maxy;
	ans%=mod;
	return ans;
}
int init(int N,int X[],int Y[]){
	n=N;
	for(int i = 0; i < n; i++){
		x.pb(X[i]);y.pb(Y[i]);
	}
	ll temp=Y[n-1];
	int ind=n-1;
	for(int i = n-1; i > 0; i--){
		if(temp>2000000000) break;
		temp*=X[i];
		if(Y[i-1] > temp){
			ind=i-1;temp=Y[i-1];
		}
	}
	ans=Y[ind];
	for(int i = 0; i <= ind; i++){
		ans*=X[i];ans%=mod;
	}
	build(1,0,n-1);
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

horses.cpp: In function 'int updateX(int, int)':
horses.cpp:106:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:149:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~

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