oj.uz

Submission #584212

# Submission time Handle Problem Language Result Execution time Memory
584212 2022-06-27T04:10:01 Z hibiki Horses (IOI15_horses) C++11
17 / 100
 682 ms 97836 KB 
#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++)
	{
        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);
		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();
}

Compilation message

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:127:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |  return ((que1(root1, 0, n - 1) * ybest) ) % mod;
      |                                            ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 312 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 312 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 312 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 312 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 312 KB Output is correct
23 Incorrect 2 ms 468 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 97836 KB Output is correct
2 Incorrect 432 ms 97804 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 264 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 308 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 1 ms 484 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 316 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 1 ms 468 KB Output isn't correct
24 Halted 0 ms 0 KB -