oj.uz

Submission #307299

# Submission time Handle Problem Language Result Execution time Memory
307299 2020-09-27T15:07:27 Z vipghn2003 Horses (IOI15_horses) C++14
100 / 100
 768 ms 53496 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)501*1000)
#define MOD ((int)1e9+7)
int tavan(int x,int y){int res=1;while(y){res=1LL*res*((y%2)?x:1)%MOD;x=1LL*x*x%MOD;y/=2;}return res;}
 
int n,x[N],y[N];
set <int> s;
int segMul[4*N],segMax[4*N];
 
void updateMul(int q,int val,int xl=0,int xr=n,int id=1)
{
	if(xl==xr-1)
	{
		segMul[id]=val;
		return ;
	}
	int mid=(xl+xr)/2;
	if(q<mid)updateMul(q,val,xl,mid,id*2);
	else updateMul(q,val,mid,xr,id*2+1);
	segMul[id]=1LL*segMul[id*2]*segMul[id*2+1]%MOD;
	return ;
}
 
void updateMax(int q,int val,int xl=0,int xr=n,int id=1)
{
	if(xl==xr-1)
	{
		segMax[id]=val;
		return ;
	}
	int mid=(xl+xr)/2;
	if(q<mid)updateMax(q,val,xl,mid,id*2);
	else updateMax(q,val,mid,xr,id*2+1);
	segMax[id]=max(segMax[id*2],segMax[id*2+1]);
	return ;
}
 
int queryMul(int q,int xl=0,int xr=n,int id=1)
{
	if(xr<=q)return segMul[id];
	int mid=(xl+xr)/2,res=queryMul(q,xl,mid,id*2);
	if(mid<q)res=1LL*res*queryMul(q,mid,xr,id*2+1)%MOD;
	return res;
}
 
int queryMax(int q,int xl=0,int xr=n,int id=1)
{
	if(q<=xl)return segMax[id];
	int mid=(xl+xr)/2,res=queryMax(q,mid,xr,id*2+1);
	if(q<mid)res=max(res,queryMax(q,xl,mid,id*2));
	return res;
}
 
int solve()
{
	vector <int> vec;
	auto it=s.end();it--;
	ll now=1;
	while(1)
	{
		vec.push_back(*it);
		now*=x[*it];
		if(now>=1e9+10 || it==s.begin())break;
		it--;
	}
	reverse(vec.begin(),vec.end());
	now=1;
	ll ans=0;
	for(auto u:vec)
	{
		if(u!=vec[0])now*=x[u];
		ans=max(ans,now*queryMax(u));
	}
	ans%=MOD;
	ans*=queryMul(vec[0]+1);ans%=MOD;
	return ans;
}
 
int init(int n2, int X[], int Y[])
{
	n=n2;
	for(int i=0;i<n;i++)
	{
		x[i]=X[i];y[i]=Y[i];
		if(x[i]>1 || i==0)s.insert(i);
		updateMul(i,x[i]);
		updateMax(i,y[i]);
	}
	return solve();
}
 
int updateX(int pos, int val)
{	
	x[pos]=val;
	if(x[pos]==1 && pos>0)s.erase(pos);
	else s.insert(pos);
	updateMul(pos,x[pos]);
	return solve();
}
 
int updateY(int pos, int val)
{
	y[pos]=val;
	updateMax(pos,y[pos]);
	return solve();
}

Compilation message

horses.cpp: In function 'int tavan(int, int)':
horses.cpp:7:66: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    7 | int tavan(int x,int y){int res=1;while(y){res=1LL*res*((y%2)?x:1)%MOD;x=1LL*x*x%MOD;y/=2;}return res;}
      |                                                                  ^
horses.cpp:7:80: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    7 | int tavan(int x,int y){int res=1;while(y){res=1LL*res*((y%2)?x:1)%MOD;x=1LL*x*x%MOD;y/=2;}return res;}
      |                                                                                ^
horses.cpp: In function 'void updateMul(int, int, int, int, int)':
horses.cpp:23:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   23 |  segMul[id]=1LL*segMul[id*2]*segMul[id*2+1]%MOD;
      |                                            ^
horses.cpp: In function 'int queryMul(int, int, int, int)':
horses.cpp:45:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   45 |  if(mid<q)res=1LL*res*queryMul(q,mid,xr,id*2+1)%MOD;
      |                                                ^
horses.cpp: In function 'int solve()':
horses.cpp:66:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   66 |   if(now>=1e9+10 || it==s.begin())break;
      |      ^~~
horses.cpp:79:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return ans;
      |         ^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 40952 KB Output is correct
2 Correct 554 ms 53496 KB Output is correct
3 Correct 541 ms 44664 KB Output is correct
4 Correct 626 ms 48504 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 232 ms 16632 KB Output is correct
34 Correct 232 ms 20600 KB Output is correct
35 Correct 390 ms 50232 KB Output is correct
36 Correct 392 ms 50296 KB Output is correct
37 Correct 268 ms 18808 KB Output is correct
38 Correct 300 ms 31608 KB Output is correct
39 Correct 218 ms 18680 KB Output is correct
40 Correct 360 ms 45944 KB Output is correct
41 Correct 241 ms 18680 KB Output is correct
42 Correct 253 ms 18720 KB Output is correct
43 Correct 347 ms 46200 KB Output is correct
44 Correct 354 ms 46328 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 416 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 2 ms 484 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 768 ms 42488 KB Output is correct
34 Correct 550 ms 51064 KB Output is correct
35 Correct 545 ms 44776 KB Output is correct
36 Correct 637 ms 48632 KB Output is correct
37 Correct 232 ms 20728 KB Output is correct
38 Correct 234 ms 20600 KB Output is correct
39 Correct 395 ms 50936 KB Output is correct
40 Correct 375 ms 50808 KB Output is correct
41 Correct 278 ms 18772 KB Output is correct
42 Correct 298 ms 31484 KB Output is correct
43 Correct 219 ms 18424 KB Output is correct
44 Correct 363 ms 45944 KB Output is correct
45 Correct 240 ms 18552 KB Output is correct
46 Correct 254 ms 18552 KB Output is correct
47 Correct 353 ms 46200 KB Output is correct
48 Correct 351 ms 46456 KB Output is correct
49 Correct 365 ms 23672 KB Output is correct
50 Correct 354 ms 23532 KB Output is correct
51 Correct 531 ms 52728 KB Output is correct
52 Correct 460 ms 52216 KB Output is correct
53 Correct 744 ms 22264 KB Output is correct
54 Correct 484 ms 35576 KB Output is correct
55 Correct 311 ms 19576 KB Output is correct
56 Correct 468 ms 47864 KB Output is correct
57 Correct 510 ms 20216 KB Output is correct
58 Correct 650 ms 20728 KB Output is correct
59 Correct 351 ms 46456 KB Output is correct