제출 #584226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584226		hibiki	말 (IOI15_horses)	C++11	100 / 100	748 ms	99404 KiB

horses

// #include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007;
#define pb push_back

int n, x[500005], y[500005];
set<int, greater<int>> s;

struct node
{
	long long val;
	node *l, *r;
} *root1, *root2;

node* build1(int l,int r)
{
	node *ptr = new node;
	if(l == r)
	{
		ptr->val = x[l];
		return ptr;
	}
	int mid = (l + r) / 2;
	ptr->l = build1(l, mid);
	ptr->r = build1(mid + 1, r);
	ptr->val = ptr->l->val * ptr->r->val;
    ptr->val %= mod;
    return ptr;
}

node* build2(int l,int r)
{
	node *ptr = new node;
	if(l == r)
	{
		ptr->val = y[l];
		return ptr;
	}
	int mid = (l + r) / 2;
	ptr->l = build2(l, mid);
	ptr->r = build2(mid + 1, r);
	ptr->val = max(ptr->l->val, ptr->r->val);
    return ptr;
}

int ll,rr;
long long que1(node *ptr, int l,int r)
{
    if(ll <= l && r <= rr) return ptr->val;
    if(r < ll || rr < l) return 1;
    int mid = (l + r) / 2;
    return (que1(ptr->l, l, mid) * que1(ptr->r, mid + 1, r)) % mod;
}

int que2(node *ptr, int l,int r)
{
    if(ll <= l && r <= rr) return ptr->val;
    if(r < ll || rr < l) return 0;
    int mid = (l + r) / 2;
    return max(que2(ptr->l, l, mid),que2(ptr->r, mid + 1, r));
}

int up_po,up_val;
void up1(node *ptr, int l,int r)
{
    if(l == r)
    {
        ptr->val = up_val;
        return ;
    }
    int mid = (l + r) / 2;
    if(up_po <= mid) up1(ptr->l, l, mid);
    else up1(ptr->r, mid + 1, r);
    ptr->val = ptr->l->val * ptr->r->val;
    ptr->val %= mod;
}

void up2(node *ptr, int l,int r)
{
    if(l == r)
    {
        ptr->val = up_val;
        return ;
    }
    int mid = (l + r) / 2;
    if(up_po <= mid) up2(ptr->l, l, mid);
    else up2(ptr->r, mid + 1, r);
    ptr->val = max(ptr->l->val, ptr->r->val);
}

int cal()
{
	vector<int> idx = { n };
	long long val = 1;
	for(int sidx : s)
	{
		idx.pb(sidx);
		val *= x[sidx];

		if (val > 1e9 + 5)
			break;
	}

	if(val <= 1e9 + 5 && idx.back() != 0)
		idx.pb(0);
	reverse(idx.begin(), idx.end());

	long long mx = 0, xval = 1ll;
    int best = 0, ybest = 0;
	for(int i = 0; i < idx.size() - 1; i++)
	{
        if(i != 0)
            xval *= x[idx[i]];
        ll = idx[i];
        rr = idx[i + 1] - 1;
		int ymax = que2(root2, 0, n - 1);
        ll = idx[1];
        rr = idx[i];
		// long long xval = que1(root1, 0, n - 1);
        // printf("%lld\n",xval);
		if (ymax * xval > mx)
			mx = ymax * xval, best = i, ybest = ymax;
	}

    ll = 0;
    rr = idx[best];
	return ((que1(root1, 0, n - 1) * ybest) ) % mod;
}

int init(int N, int X[], int Y[])
{
	n = N;
	for(int i = 0; i < n; i++)
		x[i] = X[i], y[i] = Y[i];

    root1 = build1(0, n - 1);
    root2 = build2(0, n - 1);

	for(int i = 0; i < n; i++)
        if(x[i] != 1)
		      s.insert(i);

	return cal();
}

int updateX(int pos, int val)
{
	x[pos] = val;
    up_po = pos;
    up_val = val;
	up1(root1, 0, n - 1);
	if (val == 1) s.erase(pos);
	else s.insert(pos);

	return cal();
}

int updateY(int pos, int val)
{
	y[pos] = val;
    up_po = pos;
    up_val = val;
	up2(root2, 0, n - 1);
	return cal();
}

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

horses.cpp: In function 'int que2(node*, int, int)':
horses.cpp:59:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   59 |     if(ll <= l && r <= rr) return ptr->val;
      |                                   ~~~~~^~~
horses.cpp: In function 'int cal()':
horses.cpp:102:7: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  102 |   if (val > 1e9 + 5)
      |       ^~~
horses.cpp:106:5: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
  106 |  if(val <= 1e9 + 5 && idx.back() != 0)
      |     ^~~
horses.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for(int i = 0; i < idx.size() - 1; i++)
      |                 ~~^~~~~~~~~~~~~~~~
horses.cpp:129:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  129 |  return ((que1(root1, 0, n - 1) * ybest) ) % mod;
      |                                            ^

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