oj.uz

Submission #417177

# Submission time Handle Problem Language Result Execution time Memory
417177 2021-06-03T12:38:40 Z Jasiekstrz Horses (IOI15_horses) C++17
100 / 100
 384 ms 49160 KB 
#include<bits/stdc++.h>
#include "horses.h"
#define fi first
#define se second
using namespace std;
const int NN=5e5;
const int PP=53e4;
const long long MOD=1e9+7;
struct Frac
{
	long long a,b;
	bool operator<(const Frac &oth) const
	{
		return a*oth.b<oth.a*b;
	}
};
int n;
int pot;
long long prod;
int tree[2*PP+10];
int x[NN+10];
int y[NN+10];
set<int> st;
long long qp(int a,int b)
{
	if(b==0)
		return 1;
	long long tmp=qp(a,b/2);
	tmp=(tmp*tmp)%MOD;
	if(b%2==1)
		return (tmp*a)%MOD;
	return tmp;
}
void add_t(int g,int c)
{
	g+=pot-1;
	tree[g]=c;
	for(g/=2;g>=1;g/=2)
		tree[g]=max(tree[2*g],tree[2*g+1]);
	return;
}
int read_t(int l,int r)
{
	int ans=0;
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ans=max(ans,tree[l++]);
		if(r%2==0)
			ans=max(ans,tree[r--]);
	}
	return ans;
}
int get_ans()
{
	Frac w={y[n],1};
	long long den=1;
	for(auto it=prev(st.end());true;it--)
	{
		den*=x[*it];
		if(den>=MOD)
			break;
		if(it==st.begin())
		{
			Frac tmp={read_t(1,(*it)-1),den};
			w=max(w,tmp);
			break;
		}
		Frac tmp={read_t(*prev(it),(*it)-1),den};
		w=max(w,tmp);
	}
	//cerr<<prod<<" "<<w.a<<" "<<w.b<<"\n";
	return (((prod*w.a)%MOD)*qp(w.b,MOD-2))%MOD;
}
int init(int N,int X[],int Y[])
{
	n=N;
	for(int i=0;i<n;i++)
	{
		x[i+1]=X[i];
		y[i+1]=Y[i];
	}
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=n;i++)
		tree[pot+i-1]=y[i];
	for(int i=pot-1;i>=1;i--)
		tree[i]=max(tree[2*i],tree[2*i+1]);
	prod=1;
	for(int i=1;i<=n;i++)
	{
		prod*=x[i];
		prod%=MOD;
		if(x[i]>1 || i==n)
			st.insert(i);
	}
	return get_ans();
}
int updateX(int pos,int val)
{
	prod=(prod*qp(x[pos+1],MOD-2))%MOD;
	prod=(prod*val)%MOD;
	x[pos+1]=val;
	st.erase(pos+1);
	if(val>1 || pos+1==n)
		st.insert(pos+1);
	return get_ans();
}
int updateY(int pos,int val)
{
	y[pos+1]=val;
	add_t(pos+1,val);
	return get_ans();
}

Compilation message

horses.cpp: In function 'int get_ans()':
horses.cpp:73:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   73 |  return (((prod*w.a)%MOD)*qp(w.b,MOD-2))%MOD;
      |                              ~~^
horses.cpp:73:41: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   73 |  return (((prod*w.a)%MOD)*qp(w.b,MOD-2))%MOD;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 37500 KB Output is correct
2 Correct 364 ms 49124 KB Output is correct
3 Correct 308 ms 40328 KB Output is correct
4 Correct 384 ms 44224 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 308 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Correct 39 ms 16196 KB Output is correct
34 Correct 37 ms 16168 KB Output is correct
35 Correct 191 ms 46500 KB Output is correct
36 Correct 215 ms 46536 KB Output is correct
37 Correct 39 ms 14380 KB Output is correct
38 Correct 96 ms 27136 KB Output is correct
39 Correct 28 ms 14184 KB Output is correct
40 Correct 202 ms 41552 KB Output is correct
41 Correct 34 ms 14180 KB Output is correct
42 Correct 31 ms 14276 KB Output is correct
43 Correct 176 ms 41980 KB Output is correct
44 Correct 182 ms 41884 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 308 KB Output is correct
24 Correct 1 ms 372 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 1 ms 308 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 316 KB Output is correct
31 Correct 2 ms 308 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Correct 235 ms 40352 KB Output is correct
34 Correct 325 ms 49160 KB Output is correct
35 Correct 282 ms 40388 KB Output is correct
36 Correct 381 ms 44132 KB Output is correct
37 Correct 37 ms 16196 KB Output is correct
38 Correct 36 ms 16176 KB Output is correct
39 Correct 204 ms 46544 KB Output is correct
40 Correct 225 ms 46440 KB Output is correct
41 Correct 37 ms 14404 KB Output is correct
42 Correct 103 ms 27172 KB Output is correct
43 Correct 28 ms 14212 KB Output is correct
44 Correct 212 ms 41596 KB Output is correct
45 Correct 26 ms 14204 KB Output is correct
46 Correct 29 ms 14276 KB Output is correct
47 Correct 181 ms 41980 KB Output is correct
48 Correct 191 ms 41960 KB Output is correct
49 Correct 120 ms 19268 KB Output is correct
50 Correct 138 ms 19188 KB Output is correct
51 Correct 272 ms 48452 KB Output is correct
52 Correct 256 ms 47940 KB Output is correct
53 Correct 175 ms 17516 KB Output is correct
54 Correct 187 ms 31196 KB Output is correct
55 Correct 111 ms 15200 KB Output is correct
56 Correct 272 ms 43456 KB Output is correct
57 Correct 102 ms 15840 KB Output is correct
58 Correct 130 ms 16412 KB Output is correct
59 Correct 205 ms 41912 KB Output is correct