oj.uz

Submission #727328

# Submission time Handle Problem Language Result Execution time Memory
727328 2023-04-20T12:03:40 Z jwvg0425 Horses (IOI15_horses) C++17
100 / 100
 431 ms 89420 KB 
#include "horses.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MOD ((i64)1e9 + 7)
 
using namespace std;
 
template <typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
constexpr int clog2(int n) { return ((n < 2) ? 1 : 1 + clog2(n / 2)); }
 
template <typename T>
class SegmentTree
{
public:
	SegmentTree() = default;
 
	template <typename M>
	SegmentTree(const M &m) : merge(m) {}
 
	void init(const vector<T> &raw_)
	{
		raw = raw_;
		n = (int)raw.size();
		int sz = (1 << (clog2(n) + 1));
		data.resize(sz);
 
		_init(raw, 1, 0, n - 1);
	}
 
	T modify(int idx, function<T(T)> modifier) { return update(idx, modifier(raw[idx])); }
	T update(int idx, const T &newVal)
	{
		raw[idx] = newVal;
		return _update(1, 0, n - 1, idx, newVal);
	}
	T query(int left, int right) { return _query(1, 0, n - 1, left, right); }
 
private:
	vector<T> raw;
	vector<T> data;
	int n;
	using Merge = function<T(const T &, const T &)>;
	Merge merge;
 
	T _init(const vector<T> &raw, int node, int start, int end)
	{
		int mid = (start + end) / 2;
		if (start == end)
			return data[node] = raw[start];
		else
			return data[node] = merge(_init(raw, node * 2, start, mid),
																_init(raw, node * 2 + 1, mid + 1, end));
	}
 
	T _update(int node, int start, int end, int index, const T &newVal)
	{
		if (index < start || index > end)
			return data[node];
 
		if (start == end)
			data[node] = newVal;
		else
		{
			int mid = (start + end) / 2;
			data[node] = merge(_update(node * 2, start, mid, index, newVal),
												 _update(node * 2 + 1, mid + 1, end, index, newVal));
		}
 
		return data[node];
	}
 
	T _query(int node, int start, int end, int left, int right)
	{
		if (left <= start && end <= right)
			return data[node];
 
		int mid = (start + end) / 2;
 
		if (mid < left)
			return _query(node * 2 + 1, mid + 1, end, left, right);
 
		if (mid + 1 > right)
			return _query(node * 2, start, mid, left, right);
 
		return merge(_query(node * 2, start, mid, left, right),
								 _query(node * 2 + 1, mid + 1, end, left, right));
	}
};
 
int n;
vector<i64> x;
vector<pair<i64, int>> y;
set<int> xp;
auto ytree = SegmentTree<pair<i64, int>>([](auto &l, auto &r)
																				 { return max(l, r); });
auto xtree = SegmentTree<i64>([](i64 l, i64 r)
															{ return (l * r) % MOD; });
 
int getAns()
{
	vector<int> xps = {n};
	i64 xi = 1;
	auto iter = xp.rbegin();
	while (iter != xp.rend() && xi < (i64)1e9)
	{
		xps.push_back(*iter);
		xi *= x[*iter];
		++iter;
	}
 
	// x 다 곱해도 1e9 안 되는 경우, 전부 봐줘야함
	if (xi < (i64)1e9 && xps.back() != 0)
		xps.push_back(0);
 
	reverse(all(xps));
 
	i64 nowX = 1;
	i64 maxX = 1;
	i64 maxY = 1;
	int ans = 0;
 
	for (int k = 1; k < xps.size(); k++)
	{
		i64 nxtX = nowX * x[xps[k - 1]];
		auto nxtY = ytree.query(xps[k - 1], xps[k] - 1);
 
		if (maxY < nxtX / maxX * nxtY.xx)
		{
			maxX = nxtX;
			maxY = nxtY.xx;
			ans = nxtY.yy;
		}
      	nowX = nxtX;
	}
 
	return (xtree.query(0, ans) * y[ans].xx) % MOD;
}
 
int init(int N, int X[], int Y[])
{
	n = N;
	x = vector<i64>(N + 1);
	y = vector<pair<i64, int>>(N + 1);
 
	for (int i = 0; i < N; i++)
	{
		x[i] = X[i];
		if (x[i] >= 2)
			xp.insert(i);
	}
 
	for (int i = 0; i < N; i++)
	{
		y[i].yy = i;
		y[i].xx = Y[i];
	}
 
	ytree.init(y);
	xtree.init(x);
 
	return getAns();
}
 
int updateX(int pos, int val)
{
	x[pos] = val;
	xtree.update(pos, val);
	if (x[pos] == 1)
		xp.erase(pos);
	else
		xp.insert(pos);
 
	return getAns();
}
 
int updateY(int pos, int val)
{
	y[pos].xx = val;
	ytree.update(pos, y[pos]);
	return getAns();
}

Compilation message

horses.cpp: In member function 'T SegmentTree<T>::_init(const std::vector<_Tp>&, int, int, int)':
horses.cpp:67:27: warning: declaration of 'raw' shadows a member of 'SegmentTree<T>' [-Wshadow]
   67 |  T _init(const vector<T> &raw, int node, int start, int end)
      |          ~~~~~~~~~~~~~~~~~^~~
horses.cpp:61:12: note: shadowed declaration is here
   61 |  vector<T> raw;
      |            ^~~
horses.cpp: In function 'int getAns()':
horses.cpp:144:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |  for (int k = 1; k < xps.size(); k++)
      |                  ~~^~~~~~~~~~~~
horses.cpp:158:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  158 |  return (xtree.query(0, ans) * y[ans].xx) % MOD;
      |                                           ^
horses.cpp: In instantiation of 'T SegmentTree<T>::_init(const std::vector<_Tp>&, int, int, int) [with T = std::pair<long long int, int>]':
horses.cpp:49:3:   required from 'void SegmentTree<T>::init(const std::vector<_Tp>&) [with T = std::pair<long long int, int>]'
horses.cpp:180:14:   required from here
horses.cpp:67:27: warning: declaration of 'raw' shadows a member of 'SegmentTree<std::pair<long long int, int> >' [-Wshadow]
   67 |  T _init(const vector<T> &raw, int node, int start, int end)
      |          ~~~~~~~~~~~~~~~~~^~~
horses.cpp:61:12: note: shadowed declaration is here
   61 |  vector<T> raw;
      |            ^~~
horses.cpp: In instantiation of 'T SegmentTree<T>::_init(const std::vector<_Tp>&, int, int, int) [with T = long long int]':
horses.cpp:49:3:   required from 'void SegmentTree<T>::init(const std::vector<_Tp>&) [with T = long long int]'
horses.cpp:181:14:   required from here
horses.cpp:67:27: warning: declaration of 'raw' shadows a member of 'SegmentTree<long long int>' [-Wshadow]
   67 |  T _init(const vector<T> &raw, int node, int start, int end)
      |          ~~~~~~~~~~~~~~~~~^~~
horses.cpp:61:12: note: shadowed declaration is here
   61 |  vector<T> raw;
      |            ^~~

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 0 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 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 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
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 0 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 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 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 444 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 3 ms 312 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 76768 KB Output is correct
2 Correct 338 ms 89420 KB Output is correct
3 Correct 330 ms 80620 KB Output is correct
4 Correct 431 ms 81900 KB Output is correct

Subtask #4
23.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 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 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 1 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 1 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 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 444 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 440 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 3 ms 312 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 2 ms 316 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 66 ms 56428 KB Output is correct
34 Correct 65 ms 56524 KB Output is correct
35 Correct 196 ms 85012 KB Output is correct
36 Correct 190 ms 84944 KB Output is correct
37 Correct 92 ms 54540 KB Output is correct
38 Correct 109 ms 67388 KB Output is correct
39 Correct 52 ms 54404 KB Output is correct
40 Correct 174 ms 81740 KB Output is correct
41 Correct 58 ms 54436 KB Output is correct
42 Correct 61 ms 54488 KB Output is correct
43 Correct 169 ms 82252 KB Output is correct
44 Correct 189 ms 82156 KB Output is correct

Subtask #5
23.0 / 23.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 0 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 1 ms 264 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 1 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 260 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 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 2 ms 316 KB Output is correct
33 Correct 347 ms 80548 KB Output is correct
34 Correct 343 ms 85812 KB Output is correct
35 Correct 325 ms 80616 KB Output is correct
36 Correct 373 ms 84456 KB Output is correct
37 Correct 66 ms 56412 KB Output is correct
38 Correct 67 ms 56488 KB Output is correct
39 Correct 195 ms 85128 KB Output is correct
40 Correct 195 ms 84936 KB Output is correct
41 Correct 88 ms 54596 KB Output is correct
42 Correct 113 ms 67404 KB Output is correct
43 Correct 55 ms 54404 KB Output is correct
44 Correct 173 ms 81788 KB Output is correct
45 Correct 70 ms 54452 KB Output is correct
46 Correct 68 ms 54524 KB Output is correct
47 Correct 164 ms 82100 KB Output is correct
48 Correct 162 ms 82096 KB Output is correct
49 Correct 193 ms 59592 KB Output is correct
50 Correct 181 ms 59524 KB Output is correct
51 Correct 295 ms 88588 KB Output is correct
52 Correct 247 ms 88072 KB Output is correct
53 Correct 385 ms 57756 KB Output is correct
54 Correct 223 ms 71244 KB Output is correct
55 Correct 168 ms 55416 KB Output is correct
56 Correct 281 ms 83532 KB Output is correct
57 Correct 206 ms 56052 KB Output is correct
58 Correct 256 ms 56576 KB Output is correct
59 Correct 165 ms 82120 KB Output is correct