답안 #955985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955985	2024-03-31T18:48:20 Z	emad234	말 (IOI15_horses)	C++17	34 / 100	1500 ms	87144 KB

horses

#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)
		{
			auto it = s.upper_bound({i, i});
			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.lower_bound({i, i});
			seg.s = (*it).l + 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);
	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:4:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    4 | #define l first
      |           ^
horses.cpp:64:14: note: in expansion of macro 'l'
   64 |    i = (*it).l;
      |              ^
horses.cpp:74:7: warning: statement has no effect [-Wunused-value]
   74 |  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:87:14: note: in expansion of macro 'r'
   87 |    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:149:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  149 |  return solve();
      |         ~~~~~^~
horses.cpp:5:11: warning: variable 'second' set but not used [-Wunused-but-set-variable]
    5 | #define r second
      |           ^~~~~~
horses.cpp:120:14: note: in expansion of macro 'r'
  120 |  int l = -1, r = -1;
      |              ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:221:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  221 |  return solve();
      |         ~~~~~^~
horses.cpp:5:11: warning: variable 'second' set but not used [-Wunused-but-set-variable]
    5 | #define r second
      |           ^~~~~~
horses.cpp:192:14: note: in expansion of macro 'r'
  192 |  int l = -1, r = -1;
      |              ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:228:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  228 |  return solve();
      |         ~~~~~^~

Subtask #1

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 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	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2392 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	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	2648 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	2492 KB	Output is correct
20	Correct	0 ms	2396 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 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	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	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	1 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	1 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	2396 KB	Output is correct
18	Correct	1 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	1 ms	2396 KB	Output is correct
22	Correct	1 ms	2392 KB	Output is correct
23	Correct	144 ms	2624 KB	Output is correct
24	Correct	36 ms	2396 KB	Output is correct
25	Correct	27 ms	2392 KB	Output is correct
26	Correct	33 ms	2652 KB	Output is correct
27	Correct	116 ms	2396 KB	Output is correct
28	Correct	57 ms	2392 KB	Output is correct
29	Correct	205 ms	2620 KB	Output is correct
30	Correct	90 ms	2628 KB	Output is correct
31	Correct	153 ms	2652 KB	Output is correct
32	Correct	170 ms	2652 KB	Output is correct

Subtask #3

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	212 ms	77288 KB	Output is correct
2	Execution timed out	1509 ms	76268 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 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	2392 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 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	0 ms	2396 KB	Output is correct
13	Correct	0 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	0 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	1 ms	2396 KB	Output is correct
22	Correct	1 ms	2396 KB	Output is correct
23	Correct	155 ms	2396 KB	Output is correct
24	Correct	35 ms	2648 KB	Output is correct
25	Correct	34 ms	2396 KB	Output is correct
26	Correct	27 ms	2396 KB	Output is correct
27	Correct	117 ms	2396 KB	Output is correct
28	Correct	59 ms	2628 KB	Output is correct
29	Correct	204 ms	2620 KB	Output is correct
30	Correct	89 ms	2392 KB	Output is correct
31	Correct	149 ms	2652 KB	Output is correct
32	Correct	182 ms	2896 KB	Output is correct
33	Execution timed out	1596 ms	80204 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	결과	실행 시간	메모리	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	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	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	0 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 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	2548 KB	Output is correct
20	Correct	1 ms	2392 KB	Output is correct
21	Correct	1 ms	2392 KB	Output is correct
22	Correct	1 ms	2396 KB	Output is correct
23	Correct	142 ms	2616 KB	Output is correct
24	Correct	35 ms	2392 KB	Output is correct
25	Correct	27 ms	2652 KB	Output is correct
26	Correct	27 ms	2648 KB	Output is correct
27	Correct	123 ms	2396 KB	Output is correct
28	Correct	58 ms	2900 KB	Output is correct
29	Correct	201 ms	2396 KB	Output is correct
30	Correct	89 ms	2628 KB	Output is correct
31	Correct	165 ms	2652 KB	Output is correct
32	Correct	177 ms	2648 KB	Output is correct
33	Correct	219 ms	80980 KB	Output is correct
34	Execution timed out	1572 ms	87144 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-