oj.uz

Submission #992991

# Submission time Handle Problem Language Result Execution time Memory
992991 2024-06-05T08:47:59 Z vjudge1 Horses (IOI15_horses) C++17
77 / 100
 1500 ms 61260 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 5e5 + 5;
using namespace std;
ll NN;
struct tree
{
	vector<pii> seg;
	ll s, e;
	void init(ll n)
	{
		NN = exp2(ceil(log2(n)));
		seg.resize(NN * 4);
	}
	ll queryMax(ll l = 1, ll r = NN, ll ind = 1)
	{
		if (l > e || r < s)
			return 0;
		if (l >= s && r <= e)
			return seg[ind].F;
		ll md = (l + r) / 2;
		return max(queryMax(l, md, ind * 2), queryMax(md + 1, r, ind * 2 + 1));
	}
	ll queryProd(ll l = 1, ll r = NN, ll ind = 1)
	{
		if (l > e || r < s)
			return 1;
		if (l >= s && r <= e)
			return seg[ind].S;
		ll md = (l + r) / 2;
		return (queryProd(l, md, ind * 2) * queryProd(md + 1, r, ind * 2 + 1)) % mod;
	}
	void update(pii val, ll ind)
	{
		ind += NN;
		seg[ind] = val;
		while (ind /= 2)
		{
			seg[ind].F = max(seg[ind * 2].F, seg[ind * 2 + 1].F);
			seg[ind].S = (seg[ind * 2].S * seg[ind * 2 + 1].S) % mod;
		}
	}
} seg;
struct ones
{
	int l,r;
	friend bool operator<(ones a, ones b) {return a.l < b.l;}
};
 
set<ones> s;
ll x[mxN], y[mxN];
ll n;
ll solve()
{
	ll st, id = 0;
	int i = n - 1;
	while (i > 0 && id <= 100)
	{
		if (x[i] == 1)
		{
			auto it = s.upper_bound({i, INT_MAX});
			it--;
			i = (*it).l;
			id--;
		}
		i--;
		id++;
	}
	if (i == -1)
		i = 0;
	ll mx = -1, mxid = -1;
	ll prd = 1;
	for (i; i < n; i++)
	{
		if (x[i] == 1)
		{
			auto it = s.upper_bound({i, INT_MAX});
			it--;
			seg.s = i + 1, seg.e = (*it).r + 1;
			ll val = seg.queryMax();
			if (val * prd > mx)
			{
				mx = val;
				mxid = i;
				prd = 1;
			}
			i = (*it).r;
			continue;
		}
		if (prd * x[i] > mx)
		{
			mx = y[i];
			mxid = i;
			prd = 1;
			continue;
		}
		prd *= x[i];
		if (prd * y[i] > mx)
		{
			mx = y[i];
			mxid = i;
			prd = 1;
			continue;
		}
	}
	seg.s = 1;
	seg.e = mxid + 1;
	return (mx * seg.queryProd()) % mod;
}
int init(int N, int X[], int Y[])
{
	seg.init(N);
	n = N;
	for (int i = 0; i < N; i++)
	{
		y[i] = Y[i];
		x[i] = X[i];
		seg.update({Y[i], X[i]}, i);
	}
	int l = -1, r = -1;
	for (int i = 0; i < N; i++)
	{
		// s.insert({i, i});
		if (X[i] == 1)
		{
			if (l == -1)
				l = i;
			r = i;
		}
		else
		{
			if (l != -1)
			{
				s.insert({l, r});
				l = -1;r = -1;
			}
		}
	}
	if (l != -1)
	{
		s.insert({l, r});
		l = -1; r = -1;
	}
	// for (auto el : s)
	// {
	// 	fprintf(_outputFile, "%d ", el.l);
	// 	fprintf(_outputFile, "%d\n", el.r);
	// }
	return solve();
}
 
int updateX(int pos, int val)
{
	if (x[pos] != 1 && val == 1)
	{
		auto it = s.upper_bound({pos, pos});
		int l = pos, r = pos;
		if (it != s.end() && (*it).l == pos + 1)
		{
			l = pos, r = (*it).r;
			s.erase(it);
		}
		s.insert({l, r});
		it = s.lower_bound({l, r});
		auto p = s.lower_bound({l, r});
		if (it != s.begin())
		{
			it--;
			if ((*it).r == l - 1)
			{
				l = (*it).l;
				s.erase(it);
				s.erase(s.lower_bound({pos, pos}));
				s.insert({l, r});
			}
		}
	}
	if (x[pos] == 1 && val != 1)
	{
		auto it = s.upper_bound({pos, 0});
		it--;
		ll l = (*it).l, r = pos - 1, l1 = pos + 1, r1 = (*it).r;
		s.erase(it);
		if (l <= r)
			s.insert({l, r});
		if (l1 <= r1)
			s.insert({l1, r1});
	}
	x[pos] = val;
	seg.update({y[pos], x[pos]}, pos);
	return solve();
}
 
int updateY(int pos, int val)
{
	y[pos] = val;
	seg.update({y[pos], x[pos]}, pos);
	return solve();
}

Compilation message

horses.cpp: In member function 'void tree::init(long long int)':
horses.cpp:17:12: warning: conversion from 'double' to 'long long int' may change value [-Wfloat-conversion]
   17 |   NN = exp2(ceil(log2(n)));
      |        ~~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:61:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   61 |  int i = n - 1;
      |          ~~^~~
horses.cpp:78:7: warning: statement has no effect [-Wunused-value]
   78 |  for (i; i < n; i++)
      |       ^
horses.cpp:60:5: warning: unused variable 'st' [-Wunused-variable]
   60 |  ll st, id = 0;
      |     ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:154:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  154 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:170:8: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  170 |   auto p = s.lower_bound({l, r});
      |        ^
horses.cpp:190:14: warning: narrowing conversion of 'l' from 'long long int' to 'int' [-Wnarrowing]
  190 |    s.insert({l, r});
      |              ^
horses.cpp:190:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp:190:17: warning: narrowing conversion of 'r' from 'long long int' to 'int' [-Wnarrowing]
  190 |    s.insert({l, r});
      |                 ^
horses.cpp:190:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp:192:14: warning: narrowing conversion of 'l1' from 'long long int' to 'int' [-Wnarrowing]
  192 |    s.insert({l1, r1});
      |              ^~
horses.cpp:192:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp:192:18: warning: narrowing conversion of 'r1' from 'long long int' to 'int' [-Wnarrowing]
  192 |    s.insert({l1, r1});
      |                  ^~
horses.cpp:192:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
horses.cpp:196:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  196 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:203:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  203 |  return solve();
      |         ~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 49776 KB Output is correct
2 Correct 191 ms 58444 KB Output is correct
3 Correct 136 ms 49748 KB Output is correct
4 Correct 176 ms 53588 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2492 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 2496 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 5 ms 2616 KB Output is correct
24 Correct 2 ms 2392 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 5 ms 2600 KB Output is correct
28 Correct 4 ms 2396 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 1 ms 2392 KB Output is correct
32 Correct 3 ms 2392 KB Output is correct
33 Correct 214 ms 49156 KB Output is correct
34 Correct 87 ms 49000 KB Output is correct
35 Correct 111 ms 55888 KB Output is correct
36 Correct 109 ms 55872 KB Output is correct
37 Correct 203 ms 47148 KB Output is correct
38 Correct 259 ms 59732 KB Output is correct
39 Correct 78 ms 46844 KB Output is correct
40 Correct 89 ms 51024 KB Output is correct
41 Correct 83 ms 47116 KB Output is correct
42 Correct 95 ms 47188 KB Output is correct
43 Correct 84 ms 51284 KB Output is correct
44 Correct 85 ms 51280 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2504 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2392 KB Output is correct
23 Correct 5 ms 2392 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 5 ms 2396 KB Output is correct
28 Correct 4 ms 2396 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2612 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 2 ms 2392 KB Output is correct
33 Correct 137 ms 49748 KB Output is correct
34 Correct 200 ms 58440 KB Output is correct
35 Correct 134 ms 49748 KB Output is correct
36 Correct 155 ms 53584 KB Output is correct
37 Correct 204 ms 48980 KB Output is correct
38 Correct 97 ms 48980 KB Output is correct
39 Correct 123 ms 55880 KB Output is correct
40 Correct 102 ms 55764 KB Output is correct
41 Correct 224 ms 47148 KB Output is correct
42 Correct 277 ms 60020 KB Output is correct
43 Correct 84 ms 46932 KB Output is correct
44 Correct 94 ms 51024 KB Output is correct
45 Correct 85 ms 46928 KB Output is correct
46 Correct 100 ms 47188 KB Output is correct
47 Correct 88 ms 51332 KB Output is correct
48 Correct 90 ms 51164 KB Output is correct
49 Correct 1458 ms 51912 KB Output is correct
50 Correct 234 ms 52076 KB Output is correct
51 Correct 192 ms 57696 KB Output is correct
52 Correct 157 ms 57340 KB Output is correct
53 Correct 1311 ms 50364 KB Output is correct
54 Execution timed out 1529 ms 61260 KB Time limit exceeded
55 Halted 0 ms 0 KB -