oj.uz

Submission #560964

# Submission time Handle Problem Language Result Execution time Memory
560964 2022-05-12T05:53:42 Z AriaH Horses (IOI15_horses) C++17
17 / 100
 440 ms 33820 KB 
#include "horses.h"
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;

int n, A[N], B[N];

struct node
{
	ll z, mx, my;
	void init(int a, int b)
	{
		z = a;
		mx = a;
		my = b;
	}
	friend node operator | (node a, node b)
	{
		node ret;
		ret.z = a.z * b.z % mod;
		ret.mx = max(a.mx, b.mx);
		ret.my = max(a.my, b.my);
		return ret;
	}
} seg[N << 2];

void build(int v = 1, int tl = 0, int tr = n - 1)
{
	if(tl == tr)
	{
		seg[v].init(A[tl], B[tl]);
		return;
	}
	int mid = (tl + tr) >> 1;
	build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
	seg[v] = seg[v << 1] | seg[v << 1 | 1];
}

void Change(int p, int v = 1, int tl = 0, int tr = n - 1)
{
	if(tl == tr)
	{
		seg[v].init(A[p], B[p]);
		return;
	}
	int mid = (tl + tr) >> 1;
	if(p <= mid) Change(p, v << 1, tl, mid);
	else Change(p, v << 1 | 1, mid + 1, tr);
	seg[v] = seg[v << 1] | seg[v << 1 | 1];
}

pii get(int pos, int v = 1, int tl = 0, int tr = n - 1)
{
	if(tl > pos) return Mp(-1, -1);
	if(seg[v].mx == 1) return Mp(tl, seg[v].my);
	if(tl == tr) return Mp(tl, B[tl]);
	int mid = (tl + tr) >> 1;
	pii cu = get(pos, v << 1 | 1, mid + 1, tr);
	if(A[cu.F] > 1)
	{
		return cu;
	}
	pii now = get(pos, v << 1, tl, mid);
	return Mp(now.F, max(now.S, cu.S));
}

ll ask(int l, int r, int v = 1, int tl = 0, int tr = n - 1)
{
	if(l > tr || r < tl || l > r) return 1;
	if(l <= tl && tr <= r) return seg[v].z;
	int mid = (tl + tr) >> 1;
	return ask(l, r, v << 1, tl, mid) * ask(l, r, v << 1 | 1, mid + 1, tr) % mod;
}

int solve()
{
	int id = n - 1;
	ll zarb = 1, best = 0;
	while(id >= 0)
	{
		pii now = get(id);
		zarb *= A[now.F];
		best = max(best, (ll)now.S);
		assert(id > now.F - 1);
		id = now.F - 1;
		assert(id >= -1);
		///printf("id = %d best = %lld zarb = %lld\n", id, best, zarb);
		if(zarb >= mod) break;
		best *= A[now.F];
	}
	best %= mod;
	if(id == -1)
	{
		return best;
	}
	return best * ask(0, id) % mod;
}

int init(int _N, int X[], int Y[])
{
	n = _N;
	for(int i = 0; i < n; i ++) A[i] = X[i], B[i] = Y[i];
	build();
	return solve();
}

int updateX(int pos, int val)
{
	assert(val > 0);
	A[pos] = val;
	Change(pos);
	return solve();
}

int updateY(int pos, int val)
{
	assert(val > 0);
	B[pos] = val;
	Change(pos);
	return solve();
}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:114:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |   return best;
      |          ^~~~
horses.cpp:116:27: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |  return best * ask(0, id) % mod;
      |         ~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 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 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 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 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 296 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 440 ms 33820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 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 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 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -