답안 #43563 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43563	2018-03-17T19:15:54 Z	PowerOfNinjaGo	말 (IOI15_horses)	C++14	17 / 100	1434 ms	73556 KB

horses

//Power Of Ninja Go
#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;
	for(auto it = bst.rbegin(); it != bst.rend() && product<1e9; it++)
	{
		tmp.pb(*it);
		product *= x[*it];
	}
	reverse(tmp.begin(), tmp.end());
	if(tmp.empty()) return ask(most, 1, n, 2);
	ll best = ask(most, 1, tmp[0]-1, 2);
	ll run = 1;
	int q = tmp.size();
	for(int i = 0; i< q; i++)
	{
		//printf("%d", tmp[i]);
		run *= x[tmp[i]];
		int rend = i+1<q?tmp[i+1]:n+1;
		best = max(best, 1LL*run*ask(most, tmp[i], rend-1, 2));
		//printf("(%lld)", run*ask(most, tmp[i], rend-1, 2));
	}
	//best %= md;
	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:25:19: warning: conversion to 'int' from 'll {aka 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:27: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:16:11: note: shadowed declaration is here
 const int md = 1e9 + 7;
           ^
horses.cpp:27: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:19: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:42: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:16:11: note: shadowed declaration is here
 const int md = 1e9 + 7;
           ^
horses.cpp:47:5: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  ll x = ask(st, i, j, md, 2*p, L, M);
     ^
horses.cpp:19:5: note: shadowed declaration is here
 int x[4*maxn];
     ^
horses.cpp:48: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:20:5: note: shadowed declaration is here
 int y[4*maxn];
     ^
horses.cpp: In function 'int query()':
horses.cpp:63:42: 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:66:19: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int q = tmp.size();
                   ^

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	1 ms	356 KB	Output is correct
3	Correct	1 ms	424 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	1 ms	524 KB	Output is correct
6	Correct	1 ms	544 KB	Output is correct
7	Correct	1 ms	544 KB	Output is correct
8	Correct	1 ms	548 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	712 KB	Output is correct
13	Correct	2 ms	712 KB	Output is correct
14	Correct	1 ms	712 KB	Output is correct
15	Correct	1 ms	712 KB	Output is correct
16	Correct	1 ms	712 KB	Output is correct
17	Correct	1 ms	712 KB	Output is correct
18	Correct	1 ms	712 KB	Output is correct
19	Correct	1 ms	712 KB	Output is correct
20	Correct	1 ms	712 KB	Output is correct

Subtask #2
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	712 KB	Output is correct
2	Correct	1 ms	712 KB	Output is correct
3	Correct	1 ms	712 KB	Output is correct
4	Correct	1 ms	712 KB	Output is correct
5	Correct	1 ms	712 KB	Output is correct
6	Correct	1 ms	712 KB	Output is correct
7	Correct	1 ms	712 KB	Output is correct
8	Correct	2 ms	712 KB	Output is correct
9	Correct	2 ms	712 KB	Output is correct
10	Correct	1 ms	712 KB	Output is correct
11	Correct	1 ms	712 KB	Output is correct
12	Correct	1 ms	712 KB	Output is correct
13	Correct	1 ms	712 KB	Output is correct
14	Correct	1 ms	712 KB	Output is correct
15	Correct	1 ms	712 KB	Output is correct
16	Correct	1 ms	712 KB	Output is correct
17	Correct	2 ms	712 KB	Output is correct
18	Correct	1 ms	712 KB	Output is correct
19	Correct	1 ms	712 KB	Output is correct
20	Correct	1 ms	712 KB	Output is correct
21	Correct	1 ms	712 KB	Output is correct
22	Correct	1 ms	712 KB	Output is correct
23	Incorrect	3 ms	716 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #3
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1434 ms	49452 KB	Output is correct
2	Correct	851 ms	62124 KB	Output is correct
3	Correct	890 ms	65928 KB	Output is correct
4	Incorrect	995 ms	73556 KB	Output isn't correct

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	73556 KB	Output is correct
2	Correct	1 ms	73556 KB	Output is correct
3	Correct	1 ms	73556 KB	Output is correct
4	Correct	1 ms	73556 KB	Output is correct
5	Correct	2 ms	73556 KB	Output is correct
6	Correct	1 ms	73556 KB	Output is correct
7	Correct	1 ms	73556 KB	Output is correct
8	Correct	2 ms	73556 KB	Output is correct
9	Correct	1 ms	73556 KB	Output is correct
10	Correct	1 ms	73556 KB	Output is correct
11	Correct	1 ms	73556 KB	Output is correct
12	Correct	1 ms	73556 KB	Output is correct
13	Correct	1 ms	73556 KB	Output is correct
14	Correct	1 ms	73556 KB	Output is correct
15	Correct	1 ms	73556 KB	Output is correct
16	Correct	1 ms	73556 KB	Output is correct
17	Correct	1 ms	73556 KB	Output is correct
18	Correct	2 ms	73556 KB	Output is correct
19	Correct	1 ms	73556 KB	Output is correct
20	Correct	1 ms	73556 KB	Output is correct
21	Correct	1 ms	73556 KB	Output is correct
22	Correct	1 ms	73556 KB	Output is correct
23	Incorrect	4 ms	73556 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	73556 KB	Output is correct
2	Correct	1 ms	73556 KB	Output is correct
3	Correct	1 ms	73556 KB	Output is correct
4	Correct	1 ms	73556 KB	Output is correct
5	Correct	1 ms	73556 KB	Output is correct
6	Correct	1 ms	73556 KB	Output is correct
7	Correct	1 ms	73556 KB	Output is correct
8	Correct	1 ms	73556 KB	Output is correct
9	Correct	2 ms	73556 KB	Output is correct
10	Correct	1 ms	73556 KB	Output is correct
11	Correct	1 ms	73556 KB	Output is correct
12	Correct	1 ms	73556 KB	Output is correct
13	Correct	1 ms	73556 KB	Output is correct
14	Correct	1 ms	73556 KB	Output is correct
15	Correct	1 ms	73556 KB	Output is correct
16	Correct	1 ms	73556 KB	Output is correct
17	Correct	2 ms	73556 KB	Output is correct
18	Correct	1 ms	73556 KB	Output is correct
19	Correct	1 ms	73556 KB	Output is correct
20	Correct	1 ms	73556 KB	Output is correct
21	Correct	1 ms	73556 KB	Output is correct
22	Correct	1 ms	73556 KB	Output is correct
23	Incorrect	3 ms	73556 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

답안 #43563

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 0 / 17.0

Subtask #3 0 / 20.0

Subtask #4 0 / 23.0

Subtask #5 0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
0 / 17.0

Subtask #3
0 / 20.0

Subtask #4
0 / 23.0

Subtask #5
0 / 23.0