oj.uz

Submission #118661

# Submission time Handle Problem Language Result Execution time Memory
118661 2019-06-19T10:37:51 Z roseanne_pcy Horses (IOI15_horses) C++14
100 / 100
 1262 ms 61816 KB 
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "horses.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 500005;
const int md = 1e9 + 7;
ll prod[4*maxn];
ll most[4*maxn];
int x[4*maxn];
int y[4*maxn];
int n;
int mul(ll a, ll b)
{
	a %= md; b %= md;
	return (1LL*a*b)%md;
}
void update(ll *st, int x, int dx, int md, int p = 1, int L = 1, int R = n)
{
	if(L> x || R< x) return;
	if(L == R && L == x)
	{
		st[p] = dx;
		return;
	}
	int M = (L+R)/2;
	//printf("%d %d %d\n", L, R, M);
	//system("pause");
	update(st, x, dx, md, 2*p, L, M); update(st, x, dx, md, 2*p+1, M+1, R);
	if(md == 1) st[p] = mul(st[2*p], st[2*p+1]);
	else st[p] = max(st[2*p], st[2*p+1]);
}
ll ask(ll *st, int i, int j, int md, int p = 1, int L = 1, int R = n)
{
	if(i> R || j< L) return 1;
	if(i<= L && R<= j) return st[p];
	int M = (L+R)/2;
	ll x = ask(st, i, j, md, 2*p, L, M);
	ll y = ask(st, i, j, md, 2*p+1, M+1, R);
	if(md == 1) return mul(x, y);
	else return max(x, y);
}
set<int> bst;
int query()
{
	vi tmp;
	ll product = 1;
	int bef = -1;
	for(auto it = bst.rbegin(); it != bst.rend(); it++)
	{
		if(x[*it]*product<= 1e9)
		{
			product *= x[*it];
			tmp.pb(*it);
		}
		else
		{
			bef = *it;
			break;
		}
	}
	reverse(tmp.begin(), tmp.end());
	if(tmp.empty()) return ask(most, 1, n, 2);
	int q = tmp.size();
	if(bef == -1)
	{
		ll best = ask(most, 1, tmp[0]-1, 2);
		ll run = 1;
		for(int i = 0; i< q; i++)
		{
			run *= x[tmp[i]];
			int rend = i+1< q?tmp[i+1]:n+1;
			best = max(best, run*ask(most, tmp[i], rend-1, 2));
		}
		return best%md;
	}
	ll best = ask(most, bef, tmp[0]-1, 2);
	ll run = 1;
	for(int i = 0; i< q; i++)
	{
		run *= x[tmp[i]];
		int rend = i+1<q?tmp[i+1]:n+1;
		best = max(best, run*ask(most, tmp[i], rend-1, 2));
	}
	return mul(best, ask(prod, 1, tmp[0]-1, 1));
}
int init(int N, int X[], int Y[])
{
	n = N;
	for(int i = 1; i<= n; i++) x[i] = X[i-1], y[i] = Y[i-1];
	for(int i = 1; i<= N; i++) update(prod, i, x[i], 1);
	for(int i = 1; i<= N; i++) update(most, i, y[i], 2);
	for(int i = 1; i<= N; i++) if(x[i]> 1) bst.insert(i);
	return query();
}
int updateX(int pos, int val)
{
	pos++;
	x[pos] = val;
	if(val> 1) bst.insert(pos);
	else bst.erase(pos);
	update(prod, pos, val, 1);
	return query();
}
int updateY(int pos, int val)
{
	pos++;
	y[pos] = val;
	update(most, pos, val, 2);
	return query();
}

Compilation message

horses.cpp: In function 'int mul(ll, ll)':
horses.cpp:24:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (1LL*a*b)%md;
         ~~~~~~~~~^~~
horses.cpp: In function 'void update(ll*, int, int, int, int, int, int)':
horses.cpp:26:75: warning: declaration of 'md' shadows a global declaration [-Wshadow]
 void update(ll *st, int x, int dx, int md, int p = 1, int L = 1, int R = n)
                                                                           ^
horses.cpp:15:11: note: shadowed declaration is here
 const int md = 1e9 + 7;
           ^~
horses.cpp:26:75: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 void update(ll *st, int x, int dx, int md, int p = 1, int L = 1, int R = n)
                                                                           ^
horses.cpp:18:5: note: shadowed declaration is here
 int x[4*maxn];
     ^
horses.cpp: In function 'll ask(ll*, int, int, int, int, int, int)':
horses.cpp:41:69: warning: declaration of 'md' shadows a global declaration [-Wshadow]
 ll ask(ll *st, int i, int j, int md, int p = 1, int L = 1, int R = n)
                                                                     ^
horses.cpp:15:11: note: shadowed declaration is here
 const int md = 1e9 + 7;
           ^~
horses.cpp:46:5: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  ll x = ask(st, i, j, md, 2*p, L, M);
     ^
horses.cpp:18:5: note: shadowed declaration is here
 int x[4*maxn];
     ^
horses.cpp:47:5: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  ll y = ask(st, i, j, md, 2*p+1, M+1, R);
     ^
horses.cpp:19:5: note: shadowed declaration is here
 int y[4*maxn];
     ^
horses.cpp: In function 'int query()':
horses.cpp:59:12: warning: conversion to 'double' from 'll {aka long long int}' may alter its value [-Wconversion]
   if(x[*it]*product<= 1e9)
      ~~~~~~^~~~~~~~
horses.cpp:71:28: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  if(tmp.empty()) return ask(most, 1, n, 2);
                         ~~~^~~~~~~~~~~~~~~
horses.cpp:72:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int q = tmp.size();
          ~~~~~~~~^~
horses.cpp:83:14: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   return best%md;
          ~~~~^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1262 ms 53020 KB Output is correct
2 Correct 748 ms 61816 KB Output is correct
3 Correct 760 ms 52928 KB Output is correct
4 Correct 876 ms 56696 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 14 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 4 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 7 ms 384 KB Output is correct
28 Correct 5 ms 512 KB Output is correct
29 Correct 4 ms 384 KB Output is correct
30 Correct 3 ms 512 KB Output is correct
31 Correct 6 ms 512 KB Output is correct
32 Correct 7 ms 512 KB Output is correct
33 Correct 331 ms 28720 KB Output is correct
34 Correct 330 ms 28908 KB Output is correct
35 Correct 499 ms 59128 KB Output is correct
36 Correct 496 ms 59176 KB Output is correct
37 Correct 399 ms 27148 KB Output is correct
38 Correct 408 ms 39672 KB Output is correct
39 Correct 320 ms 26732 KB Output is correct
40 Correct 505 ms 54132 KB Output is correct
41 Correct 373 ms 26948 KB Output is correct
42 Correct 388 ms 26872 KB Output is correct
43 Correct 544 ms 54692 KB Output is correct
44 Correct 479 ms 54648 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 300 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 432 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 4 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 7 ms 512 KB Output is correct
28 Correct 4 ms 512 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 4 ms 512 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 6 ms 384 KB Output is correct
33 Correct 1211 ms 52980 KB Output is correct
34 Correct 724 ms 61660 KB Output is correct
35 Correct 759 ms 52872 KB Output is correct
36 Correct 867 ms 56696 KB Output is correct
37 Correct 337 ms 28792 KB Output is correct
38 Correct 371 ms 28764 KB Output is correct
39 Correct 511 ms 59128 KB Output is correct
40 Correct 494 ms 59016 KB Output is correct
41 Correct 408 ms 26884 KB Output is correct
42 Correct 413 ms 39728 KB Output is correct
43 Correct 320 ms 26620 KB Output is correct
44 Correct 482 ms 54068 KB Output is correct
45 Correct 365 ms 26744 KB Output is correct
46 Correct 390 ms 26780 KB Output is correct
47 Correct 470 ms 54648 KB Output is correct
48 Correct 499 ms 54532 KB Output is correct
49 Correct 578 ms 31864 KB Output is correct
50 Correct 527 ms 31864 KB Output is correct
51 Correct 754 ms 60960 KB Output is correct
52 Correct 616 ms 60524 KB Output is correct
53 Correct 1250 ms 30280 KB Output is correct
54 Correct 728 ms 43780 KB Output is correct
55 Correct 456 ms 27856 KB Output is correct
56 Correct 627 ms 55932 KB Output is correct
57 Correct 844 ms 28468 KB Output is correct
58 Correct 1084 ms 29064 KB Output is correct
59 Correct 471 ms 54668 KB Output is correct