oj.uz

Submission #956004

# Submission time Handle Problem Language Result Execution time Memory
956004 2024-03-31T19:14:48 Z emad234 Horses (IOI15_horses) C++17
17 / 100
 1500 ms 45896 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define l first
#define r second
#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;
set<pii> 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) id--;
		while(x[i] == 1 && i > 0)
		{
			i--;
		}
		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.lower_bound({i, i});
			seg.s = (*it).l + 1, seg.e = (*it).r + 1;
			ll val = 0;
			for(int j = i;j < n;j++){
				if(x[j] != 1) break;
				val = max(y[j],val);
			}
			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);
	s.clear();
	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 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:19:12: warning: conversion from 'double' to 'long long int' may change value [-Wfloat-conversion]
   19 |   NN = exp2(ceil(log2(n)));
      |        ~~~~^~~~~~~~~~~~~~~
horses.cpp: In function 'long long int solve()':
horses.cpp:57:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   57 |  int i = n - 1;
      |          ~~^~~
horses.cpp:72:7: warning: statement has no effect [-Wunused-value]
   72 |  for (i; i < n; i++)
      |       ^
horses.cpp:5:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    5 | #define r second
      |           ^
horses.cpp:89:14: note: in expansion of macro 'r'
   89 |    i = (*it).r;
      |              ^
horses.cpp:56:5: warning: unused variable 'st' [-Wunused-variable]
   56 |  ll st, id = 0;
      |     ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:151:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  151 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:223:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  223 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:230:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  230 |  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 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 0 ms 2396 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 2396 KB Output is correct
11 Correct 1 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 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2408 KB Output is correct

Subtask #2
0 / 17.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 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2500 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 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 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 0 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 0 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2648 KB Output is correct
23 Correct 7 ms 2396 KB Output is correct
24 Correct 7 ms 2396 KB Output is correct
25 Correct 2 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 6 ms 2396 KB Output is correct
28 Correct 27 ms 2396 KB Output is correct
29 Correct 4 ms 2392 KB Output is correct
30 Incorrect 2 ms 2396 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 45896 KB Output is correct
2 Execution timed out 1565 ms 45152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
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 1 ms 2392 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 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 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 1 ms 2736 KB Output is correct
16 Correct 0 ms 2648 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 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 7 ms 2600 KB Output is correct
24 Correct 6 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 6 ms 2396 KB Output is correct
28 Correct 27 ms 2616 KB Output is correct
29 Correct 3 ms 2396 KB Output is correct
30 Incorrect 2 ms 2396 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 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 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 0 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 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 2392 KB Output is correct
23 Correct 6 ms 2396 KB Output is correct
24 Correct 7 ms 2392 KB Output is correct
25 Correct 2 ms 2396 KB Output is correct
26 Correct 2 ms 2396 KB Output is correct
27 Correct 6 ms 2396 KB Output is correct
28 Correct 28 ms 2396 KB Output is correct
29 Correct 3 ms 2396 KB Output is correct
30 Incorrect 2 ms 2396 KB Output isn't correct
31 Halted 0 ms 0 KB -