제출 #126072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126072		baluteshih	말 (IOI15_horses)	C++14	100 / 100	234 ms	79224 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll MOD=1e9+7;

ll cross(ll a,ll aB,ll b,ll bB,ll &B)
{
	if(aB||bB||a*b>MOD) B=1;
	else B=0;
	return a*b%MOD;
}

ll n,y[500005];

struct node
{
	ll crs,mx,L,R,Lb,Rb,B;
	node operator+(const node &a)const{
		node re;
		re.crs=cross(crs,B,a.crs,a.B,re.B);
		if(Rb||a.Lb||R*a.L>MOD||R*a.L*y[a.mx]>=y[mx])
		{
			re.mx=a.mx;
			re.L=cross(crs,B,a.L,a.Lb,re.Lb);
			re.R=a.R,re.Rb=a.Rb;
		}
		else
		{
			re.mx=mx;
			re.L=L,re.Lb=Lb;
			re.R=cross(a.crs,a.B,R,Rb,re.Rb);
		}
		return re;
	}	
}seg[2000000];

void build(ll l,ll r,ll rt,int X[])
{
	if(l==r)
		return seg[rt]=node{(ll)X[l],l,(ll)X[l],1LL,0LL,0LL,0LL},void();
	ll m=l+r>>1;
	build(l,m,rt<<1,X),build(m+1,r,rt<<1|1,X);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

void modifyx(ll x,ll l,ll r,ll rt,ll v)
{
	if(l==r)
		return seg[rt]=node{v,l,v,1LL,0LL,0LL,0LL},void();
	ll m=l+r>>1;
	if(x<=m) modifyx(x,l,m,rt<<1,v);
	else modifyx(x,m+1,r,rt<<1|1,v);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

void modifyy(ll x,ll l,ll r,ll rt,ll v)
{
	if(l==r)
		return y[x]=v,void();
	ll m=l+r>>1;
	if(x<=m) modifyy(x,l,m,rt<<1,v);
	else modifyy(x,m+1,r,rt<<1|1,v);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

ll query(ll L,ll R,ll l,ll r,ll rt)
{
	if(L<=l&&R>=r)
		return seg[rt].crs;
	ll m=l+r>>1;
	if(R<=m) return query(L,R,l,m,rt<<1);
	if(L>m) return query(L,R,m+1,r,rt<<1|1);
	return query(L,R,l,m,rt<<1)*query(L,R,m+1,r,rt<<1|1)%MOD;
}

int init(int N, int X[], int Y[])
{
	n=N;
	for(int i=0;i<N;++i)
		y[i]=Y[i];
	build(0,n-1,1,X);
	return y[seg[1].mx]*query(0,seg[1].mx,0,n-1,1)%MOD;
}

int updateX(int pos, int val)
{
	modifyx(pos,0,n-1,1,val);
	return y[seg[1].mx]*query(0,seg[1].mx,0,n-1,1)%MOD;
}

int updateY(int pos, int val)
{
	modifyy(pos,0,n-1,1,val);
	return y[seg[1].mx]*query(0,seg[1].mx,0,n-1,1)%MOD;
}

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

horses.cpp: In function 'void build(ll, ll, ll, int*)':
horses.cpp:53:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~
horses.cpp: In function 'void modifyx(ll, ll, ll, ll, ll)':
horses.cpp:62:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~
horses.cpp: In function 'void modifyy(ll, ll, ll, ll, ll)':
horses.cpp:72:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~
horses.cpp: In function 'll query(ll, ll, ll, ll, ll)':
horses.cpp:82:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1;
       ~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:94:48: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return y[seg[1].mx]*query(0,seg[1].mx,0,n-1,1)%MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:100:48: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return y[seg[1].mx]*query(0,seg[1].mx,0,n-1,1)%MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:106:48: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return y[seg[1].mx]*query(0,seg[1].mx,0,n-1,1)%MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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