oj.uz

Submission #789451

# Submission time Handle Problem Language Result Execution time Memory
789451 2023-07-21T12:03:51 Z Blagoj Horses (IOI15_horses) C++17
17 / 100
 454 ms 72184 KB 
#include <bits/stdc++.h>
#include "horses.h"

using namespace std;

#define ll long long 

ll n, x[1500000], y[1500000], mod = 10e9 + 7;

struct SegmentTree {
	vector<ll> mul;
	vector<pair<ll, ll>> mx;

	void init() {
		mx.resize(n * 3, {0, 0});
		mul.resize(n * 3, 1);
	}

	void build(int k, int l, int r) {
		if (l == r) {
			mx[k] = { y[l], l };
			mul[k] = x[l];
			return;
		}
		build(k * 2, l, (l + r) / 2);
		build(k * 2 + 1, (l + r) / 2 + 1, r);
		mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
        mul[k] = mul[k * 2] * mul[k * 2 + 1];
		mul[k] %= mod;
    }

	void update(int k, int l, int r, int i, ll v, bool t) {
		if (l > i || r < i) return;
		if (l == r) {
			if (!t) mx[k].first = v;
			else mul[k] = v;
			return;
		}
		update(k * 2, l, (l + r) / 2, i, v, t);
		update(k * 2 + 1, (l + r) / 2 + 1, r, i, v, t);
		mx[k] = max(mx[k * 2], mx[k * 2 + 1]);
		mul[k] = mul[k * 2] * mul[k * 2 + 1];
		mul[k] %= mod;
	}

	ll getX(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return 1;
		if (i <= l && r <= j) return mul[k];
		return (getX(k * 2, l, (l + r) / 2, i, j) * getX(k * 2 + 1, (l + r) / 2 + 1, r, i, j)) % mod;
	}

	pair<ll, ll> getY(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return {0, 0};
		if (i <= l && r <= j) return mx[k];
		return max( getY(k * 2, l, (l + r) / 2, i, j), getY(k * 2 + 1, (l + r) / 2 + 1, r, i, j) );
	}

} sgt;

set<int> s;

ll solve() {
	auto itf = --s.end(), its = --s.end();
	itf--;
	ll val = -1, id = n;
	for (int i = 0; i < 32 && its != s.begin(); i++) {
		pair<ll, ll> t = sgt.getY(1, 0, n - 1, *itf, *its - 1);
		if (t.first > val) {
			val = t.first;
			id = t.second;
		}
		val *= x[*itf];
		if (val > 2e9 || itf == s.begin()) break;
		its--;
		itf--;
	}
	return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % 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]; 
		if (x[i] != 1) s.insert(i);
	}
	s.insert(0);
	s.insert(n);
	sgt.init();
	sgt.build(1, 0, n - 1);
	return solve();
}

int updateX(int pos, int val) {	
	if (x[pos] != 1 && pos != 0) s.erase(pos);
	x[pos] = val;
	sgt.update(1, 0, n - 1, pos, val, 1);
	if (val != 1) s.insert(pos);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	sgt.update(1, 0, n -  1, pos, val, 0);
	return solve();
}

Compilation message

horses.cpp: In function 'long long int solve()':
horses.cpp:67:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   67 |   pair<ll, ll> t = sgt.getY(1, 0, n - 1, *itf, *its - 1);
      |                                   ~~^~~
horses.cpp:73:7: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   73 |   if (val > 2e9 || itf == s.begin()) break;
      |       ^~~
horses.cpp:77:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |  return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
      |                              ~~^~~
horses.cpp:77:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |  return 1LL * sgt.getX(1, 0, n - 1, 0, id) * y[id] % mod;
      |                                        ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:87:11: warning: conversion from 'long long int' to 'std::set<int>::value_type' {aka 'int'} may change value [-Wconversion]
   87 |  s.insert(n);
      |           ^
horses.cpp:89:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  sgt.build(1, 0, n - 1);
      |                  ~~^~~
horses.cpp:90:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:96:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |  sgt.update(1, 0, n - 1, pos, val, 1);
      |                   ~~^~~
horses.cpp:98:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   98 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:103:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  103 |  sgt.update(1, 0, n -  1, pos, val, 0);
      |                   ~~^~~~
horses.cpp:104:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  104 |  return solve();
      |         ~~~~~^~

Subtask #1
17.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 1 ms 284 KB Output is correct
4 Correct 1 ms 308 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 312 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 308 KB Output is correct
11 Correct 1 ms 308 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 1 ms 308 KB Output is correct
16 Correct 1 ms 212 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 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 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 316 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 308 KB Output is correct
15 Correct 0 ms 312 KB Output is correct
16 Correct 1 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 1 ms 212 KB Output is correct
20 Correct 1 ms 312 KB Output is correct
21 Incorrect 1 ms 316 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 232 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 312 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 312 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 316 KB Output is correct
21 Incorrect 1 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 232 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 304 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 1 ms 212 KB Output is correct
13 Correct 0 ms 312 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 0 ms 212 KB Output is correct
18 Correct 0 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 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -