oj.uz

Submission #1088351

# Submission time Handle Problem Language Result Execution time Memory
1088351 2024-09-14T09:37:12 Z Pacybwoah Horses (IOI15_horses) C++17
100 / 100
 449 ms 57040 KB 
#include "horses.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
typedef long long ll;
using namespace std;
namespace{
	int n;
	vector<int> seg;
	void build(int l, int r, int ind, vector<ll>& vec){
		if(l == r){
			seg[ind] = vec[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, ind * 2, vec);
		build(mid + 1, r, ind * 2 + 1, vec);
		seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
	}
	void modify(int l, int r, int num, int pos, int ind){
		if(l == r){
			seg[ind] = num;
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid) modify(l, mid, num, pos, ind * 2);
		else modify(mid + 1, r, num, pos, ind * 2 + 1);
		seg[ind] = max(seg[ind * 2], seg[ind * 2 + 1]);
	}
	int query(int l, int r, int start, int end, int ind){
		if(r < start || end < l) return 0;
		if(start <= l && r <= end) return seg[ind];
		int mid = (l + r) >> 1;
		return max(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
	}
	const ll mod = 1e9 + 7;
	ll power(ll a, ll b){
		if(b == 1) return a % mod;
		if(b & 1) return power(a, b - 1) * a % mod;
		ll tmp = power(a, b / 2);
		return tmp * tmp % mod;
	}
	ll inverse(ll a){
		return power(a, mod - 2);
	}
	vector<ll> x, y;
	set<int> s;
	ll prod = 1;
}

int init(int N, int X[], int Y[]) {
	n = N;
	x.resize(n + 1);
	y.resize(n + 1);
	seg.resize(4 * n + 4);
	for(int i = 1; i <= n; i++) x[i] = X[i - 1], y[i] = Y[i - 1];
	build(1, n, 1, y);
	for(int i = 1; i <= n; i++) if(x[i] > 1) s.insert(i);
	for(int i = 1; i <= n; i++) prod = prod * x[i] % mod;
	if((int)s.size() == 0){
		return seg[1];
	}
	auto iter = prev(s.end());
	ll cur = 1;
	int curpos;
	vector<int> poss;
	while(1){
		curpos = (*iter);
		poss.push_back(curpos);
		cur *= x[curpos];
		if(cur > mod) break;
		if(iter == s.begin()){
			if(curpos != 1) poss.push_back(1);
			break;
		}
		iter = prev(iter);
	}
	reverse(poss.begin(), poss.end());
	__int128_t maxi = 1, now = 1;
	int sz = poss.size();
	for(int i = 0; i < sz; i++){
		now *= x[poss[i]];
		if(i == sz - 1) maxi = max(maxi, now * query(1, n, poss[i], n, 1));
		else maxi = max(maxi, now * query(1, n, poss[i], poss[i + 1] - 1, 1));
	}
	return maxi % mod * inverse(now % mod) % mod * prod % mod;
}

int updateX(int pos, int val) {	
	pos++;
	if(x[pos] > 1) s.erase(pos);
	prod *= inverse(x[pos]);
	prod %= mod;
	x[pos] = val;
	prod *= val;
	prod %= mod;
	if(x[pos] > 1) s.insert(pos);
	if((int)s.size() == 0){
		return seg[1];
	}
	auto iter = prev(s.end());
	ll cur = 1;
	int curpos;
	vector<int> poss;
	while(1){
		curpos = (*iter);
		poss.push_back(curpos);
		cur *= x[curpos];
		if(cur > mod) break;
		if(iter == s.begin()){
			if(curpos != 1) poss.push_back(1);
			break;
		}
		iter = prev(iter);
	}
	reverse(poss.begin(), poss.end());
	__int128_t maxi = 1, now = 1;
	int sz = poss.size();
	for(int i = 0; i < sz; i++){
		now *= x[poss[i]];
		if(i == sz - 1) maxi = max(maxi, now * query(1, n, poss[i], n, 1));
		else maxi = max(maxi, now * query(1, n, poss[i], poss[i + 1] - 1, 1));
	}
	return maxi % mod * inverse(now % mod) % mod * prod % mod;
}

int updateY(int pos, int val) {
	pos++;
	modify(1, n, val, pos, 1);
	y[pos] = val;
	if((int)s.size() == 0){
		return seg[1];
	}
	auto iter = prev(s.end());
	ll cur = 1;
	int curpos;
	vector<int> poss;
	while(1){
		curpos = (*iter);
		poss.push_back(curpos);
		cur *= x[curpos];
		if(cur > mod) break;
		if(iter == s.begin()){
			if(curpos != 1) poss.push_back(1);
			break;
		}
		iter = prev(iter);
	}
	reverse(poss.begin(), poss.end());
	__int128_t maxi = 1, now = 1;
	int sz = poss.size();
	for(int i = 0; i < sz; i++){
		now *= x[poss[i]];
		if(i == sz - 1) maxi = max(maxi, now * query(1, n, poss[i], n, 1));
		else maxi = max(maxi, now * query(1, n, poss[i], poss[i + 1] - 1, 1));
	}
	return maxi % mod * inverse(now % mod) % mod * prod % mod;
}
// g++ -std=c++17 -Wall -Wextra -fsanitize=undefined -fsanitize=address -Wshadow -o run horses.cpp grader.cpp

Compilation message

horses.cpp: In function 'void {anonymous}::build(int, int, int, std::vector<long long int>&)':
horses.cpp:14:20: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   14 |    seg[ind] = vec[l];
      |                    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:82:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   82 |  int sz = poss.size();
      |           ~~~~~~~~~^~
horses.cpp:88:34: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
   88 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |                              ~~~~^~~~~
horses.cpp:88:54: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
   88 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:120:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  120 |  int sz = poss.size();
      |           ~~~~~~~~~^~
horses.cpp:126:34: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
  126 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |                              ~~~~^~~~~
horses.cpp:126:54: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  126 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:153:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  153 |  int sz = poss.size();
      |           ~~~~~~~~~^~
horses.cpp:159:34: warning: conversion from '__int128' to 'll' {aka 'long long int'} may change value [-Wconversion]
  159 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |                              ~~~~^~~~~
horses.cpp:159:54: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  159 |  return maxi % mod * inverse(now % mod) % mod * prod % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 2 ms 564 KB Output is correct
27 Correct 3 ms 500 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 1 ms 484 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 3 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 48144 KB Output is correct
2 Correct 276 ms 57040 KB Output is correct
3 Correct 274 ms 48192 KB Output is correct
4 Correct 318 ms 52080 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 432 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 432 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 3 ms 344 KB Output is correct
28 Correct 2 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 3 ms 348 KB Output is correct
33 Correct 40 ms 24060 KB Output is correct
34 Correct 39 ms 23956 KB Output is correct
35 Correct 162 ms 54352 KB Output is correct
36 Correct 152 ms 54360 KB Output is correct
37 Correct 74 ms 22108 KB Output is correct
38 Correct 86 ms 34900 KB Output is correct
39 Correct 31 ms 21848 KB Output is correct
40 Correct 143 ms 49400 KB Output is correct
41 Correct 46 ms 22108 KB Output is correct
42 Correct 59 ms 22100 KB Output is correct
43 Correct 131 ms 50000 KB Output is correct
44 Correct 130 ms 49748 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 472 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 3 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 3 ms 348 KB Output is correct
33 Correct 444 ms 48100 KB Output is correct
34 Correct 263 ms 56916 KB Output is correct
35 Correct 267 ms 48208 KB Output is correct
36 Correct 303 ms 52016 KB Output is correct
37 Correct 37 ms 24144 KB Output is correct
38 Correct 36 ms 23968 KB Output is correct
39 Correct 154 ms 54352 KB Output is correct
40 Correct 154 ms 54380 KB Output is correct
41 Correct 71 ms 22148 KB Output is correct
42 Correct 83 ms 34844 KB Output is correct
43 Correct 31 ms 21852 KB Output is correct
44 Correct 150 ms 49484 KB Output is correct
45 Correct 46 ms 22096 KB Output is correct
46 Correct 57 ms 22096 KB Output is correct
47 Correct 135 ms 49748 KB Output is correct
48 Correct 139 ms 49748 KB Output is correct
49 Correct 133 ms 26964 KB Output is correct
50 Correct 112 ms 26968 KB Output is correct
51 Correct 272 ms 56136 KB Output is correct
52 Correct 222 ms 55720 KB Output is correct
53 Correct 437 ms 25208 KB Output is correct
54 Correct 235 ms 38928 KB Output is correct
55 Correct 119 ms 22988 KB Output is correct
56 Correct 214 ms 51284 KB Output is correct
57 Correct 263 ms 23636 KB Output is correct
58 Correct 370 ms 24260 KB Output is correct
59 Correct 133 ms 49780 KB Output is correct