제출 #137879

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137879		eohomegrownapps	말 (IOI15_horses)	C++14	100 / 100	443 ms	119676 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll md = 1000000007;
vector<ll> x;
vector<ll> y;
ll n;
//overall maximum: prefix * maxy
struct Data{
	ll prefix=1; //prefix inclusive of max
	bool prefixgmd=false;
	ll suffix=1;
	bool suffixgmd=false;
	ll maxy=1;
};

Data combine(Data l, Data r){
	//first determine which has maximum
	Data ans;
	//cout<<"combine"<<endl;
	//cout<<l.prefix<<" "<<l.prefixgmd<<" "<<l.suffix<<" "<<l.suffixgmd<<" "<<l.maxy<<endl;
	//cout<<r.prefix<<" "<<r.prefixgmd<<" "<<r.suffix<<" "<<r.suffixgmd<<" "<<r.maxy<<endl;
	if (l.suffixgmd||r.prefixgmd||l.suffix*r.prefix>=md){
		//r has maximum
		ans.prefix=(((l.prefix*l.suffix)%md)*r.prefix)%md;
		ans.prefixgmd=true;
		ans.suffix=r.suffix;
		ans.suffixgmd=r.suffixgmd;
		ans.maxy=r.maxy;
	} else {
		ll rval = l.suffix*r.prefix*r.maxy;
		ll lval = l.maxy;
		if (rval>lval){
			//r has maximum
			ans.maxy=r.maxy;
			if (l.prefixgmd){
				ans.prefixgmd=true;
				ans.prefix=(((l.prefix*l.suffix)%md)*r.prefix)%md;
			} else {
				ans.prefix=(l.prefix*l.suffix);
				if (ans.prefix>=md){
					ans.prefix%=md;
					ans.prefix*=r.prefix;
					ans.prefix%=md;
					ans.prefixgmd=true;
				} else {
					ans.prefix*=r.prefix;
					if (ans.prefix>=md){
						ans.prefix%=md;
						ans.prefixgmd=true;
					} else {
						ans.prefixgmd=false;
					}
				}
				ans.prefix%=md;
			}
			ans.suffix=r.suffix;
			ans.suffixgmd=r.suffixgmd;
		} else {
			//l has maximum
			ans.maxy=l.maxy;
			ans.prefixgmd=l.prefixgmd;
			ans.prefix=l.prefix;
			if (r.suffixgmd){
				ans.suffixgmd=true;
				ans.suffix=(((l.suffix*r.prefix)%md)*r.suffix)%md;
			} else {
				ans.suffix=(l.suffix*r.prefix);
				if (ans.suffix>=md){
					ans.suffix%=md;
					ans.suffix*=r.suffix;
					ans.suffix%=md;
					ans.suffixgmd=true;
				} else {
					ans.suffix*=r.suffix;
					if (ans.suffix>=md){
						ans.suffix%=md;
						ans.suffixgmd=true;
					} else {
						ans.suffixgmd=false;
					}
				}
				ans.suffix%=md;
			}
		}
	}
	//cout<<ans.prefix<<" "<<ans.prefixgmd<<" "<<ans.suffix<<" "<<ans.suffixgmd<<" "<<ans.maxy<<endl;
	return ans;
}

struct Node{
	ll s,e,m;
	Data d;
	Node *l, *r;
	Node(ll _s, ll _e){
		s=_s;e=_e;
		m=(s+e)/2;
		if (s==e){
			d.prefix=x[s];
			d.maxy=y[s];
			return;
		}
		l=new Node(s,m);
		r=new Node(m+1,e);
		d=combine(l->d,r->d);
	}

	void update(ll pos){
		if (s==e){
			d.prefix=x[pos];
			d.maxy=y[pos];
			d.suffix=1;
			d.prefixgmd=false;
			d.suffixgmd=false;
			return;
		}
		if (pos<=m){
			l->update(pos);
		} else {
			r->update(pos);
		}
		d=combine(l->d,r->d);
	}

	Data query(ll a, ll b){
		if (a==s&&b==e){
			return d;
		}
		if (b<=m){
			return l->query(a,b);
		} else if (m<a){
			return r->query(a,b);
		} else {
			return combine(l->query(a,m),r->query(m+1,b));
		}
	}
};
Node *root;
int init(int N, int X[], int Y[]) {
	n=N;
	x=vector<ll>(X,X+n);
	y=vector<ll>(Y,Y+n);
	root = new Node(0,n-1);
	Data d = root->query(0,n-1);
	ll ans = (d.prefix*d.maxy)%md;
	return ans;
}

int updateX(int pos, int val) {
	//cout<<"x"<<endl;
	x[pos]=val;
	root->update(pos);
	Data d = root->query(0,n-1);
	ll ans = (d.prefix*d.maxy)%md;
	return ans;
}

int updateY(int pos, int val) {
	//cout<<"y"<<endl;
	y[pos]=val;
	root->update(pos);
	Data d = root->query(0,n-1);
	ll ans = (d.prefix*d.maxy)%md;
	return ans;
}

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

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:147:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return ans;
         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:156:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return ans;
         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:165:9: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return ans;
         ^~~

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