oj.uz

Submission #71552

# Submission time Handle Problem Language Result Execution time Memory
71552 2018-08-25T06:42:27 Z Sa1378 Horses (IOI15_horses) C++17
100 / 100
 979 ms 279360 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 to 'int' from 'long long int' may alter its value [-Wconversion]
 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 to 'int' from 'long long int' may alter its value [-Wconversion]
 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 to 'int' from 'long long int' may alter its value [-Wconversion]
  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 to 'int' from 'long long int' may alter its value [-Wconversion]
  if(mid<q)res=1LL*res*queryMul(q,mid,xr,id*2+1)%MOD;
                                                ^
horses.cpp: In function 'int solve()':
horses.cpp:66:15: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
   if(now>=1e9+10 || it==s.begin())break;
               ^~
horses.cpp:79:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ans;
         ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 3 ms 752 KB Output is correct
8 Correct 2 ms 812 KB Output is correct
9 Correct 3 ms 816 KB Output is correct
10 Correct 3 ms 924 KB Output is correct
11 Correct 3 ms 924 KB Output is correct
12 Correct 3 ms 924 KB Output is correct
13 Correct 3 ms 960 KB Output is correct
14 Correct 2 ms 960 KB Output is correct
15 Correct 3 ms 960 KB Output is correct
16 Correct 3 ms 960 KB Output is correct
17 Correct 2 ms 960 KB Output is correct
18 Correct 3 ms 960 KB Output is correct
19 Correct 3 ms 960 KB Output is correct
20 Correct 3 ms 960 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 960 KB Output is correct
2 Correct 3 ms 960 KB Output is correct
3 Correct 2 ms 960 KB Output is correct
4 Correct 3 ms 960 KB Output is correct
5 Correct 4 ms 960 KB Output is correct
6 Correct 3 ms 960 KB Output is correct
7 Correct 3 ms 960 KB Output is correct
8 Correct 2 ms 960 KB Output is correct
9 Correct 4 ms 960 KB Output is correct
10 Correct 3 ms 960 KB Output is correct
11 Correct 3 ms 960 KB Output is correct
12 Correct 3 ms 960 KB Output is correct
13 Correct 2 ms 964 KB Output is correct
14 Correct 3 ms 964 KB Output is correct
15 Correct 3 ms 968 KB Output is correct
16 Correct 3 ms 972 KB Output is correct
17 Correct 3 ms 976 KB Output is correct
18 Correct 3 ms 984 KB Output is correct
19 Correct 2 ms 984 KB Output is correct
20 Correct 3 ms 984 KB Output is correct
21 Correct 2 ms 996 KB Output is correct
22 Correct 3 ms 1000 KB Output is correct
23 Correct 6 ms 1004 KB Output is correct
24 Correct 5 ms 1040 KB Output is correct
25 Correct 6 ms 1092 KB Output is correct
26 Correct 4 ms 1236 KB Output is correct
27 Correct 7 ms 1236 KB Output is correct
28 Correct 5 ms 1236 KB Output is correct
29 Correct 5 ms 1236 KB Output is correct
30 Correct 3 ms 1236 KB Output is correct
31 Correct 5 ms 1240 KB Output is correct
32 Correct 5 ms 1260 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 979 ms 45652 KB Output is correct
2 Correct 729 ms 58264 KB Output is correct
3 Correct 727 ms 62036 KB Output is correct
4 Correct 838 ms 69572 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 69572 KB Output is correct
2 Correct 3 ms 69572 KB Output is correct
3 Correct 3 ms 69572 KB Output is correct
4 Correct 3 ms 69572 KB Output is correct
5 Correct 3 ms 69572 KB Output is correct
6 Correct 3 ms 69572 KB Output is correct
7 Correct 3 ms 69572 KB Output is correct
8 Correct 3 ms 69572 KB Output is correct
9 Correct 3 ms 69572 KB Output is correct
10 Correct 3 ms 69572 KB Output is correct
11 Correct 2 ms 69572 KB Output is correct
12 Correct 3 ms 69572 KB Output is correct
13 Correct 3 ms 69572 KB Output is correct
14 Correct 4 ms 69572 KB Output is correct
15 Correct 3 ms 69572 KB Output is correct
16 Correct 3 ms 69572 KB Output is correct
17 Correct 2 ms 69572 KB Output is correct
18 Correct 3 ms 69572 KB Output is correct
19 Correct 3 ms 69572 KB Output is correct
20 Correct 4 ms 69572 KB Output is correct
21 Correct 3 ms 69572 KB Output is correct
22 Correct 3 ms 69572 KB Output is correct
23 Correct 4 ms 69572 KB Output is correct
24 Correct 4 ms 69572 KB Output is correct
25 Correct 5 ms 69572 KB Output is correct
26 Correct 4 ms 69572 KB Output is correct
27 Correct 6 ms 69572 KB Output is correct
28 Correct 5 ms 69572 KB Output is correct
29 Correct 4 ms 69572 KB Output is correct
30 Correct 5 ms 69572 KB Output is correct
31 Correct 7 ms 69572 KB Output is correct
32 Correct 5 ms 69572 KB Output is correct
33 Correct 273 ms 69572 KB Output is correct
34 Correct 247 ms 69572 KB Output is correct
35 Correct 495 ms 87816 KB Output is correct
36 Correct 500 ms 98576 KB Output is correct
37 Correct 300 ms 98576 KB Output is correct
38 Correct 364 ms 98576 KB Output is correct
39 Correct 240 ms 98576 KB Output is correct
40 Correct 448 ms 111776 KB Output is correct
41 Correct 232 ms 111776 KB Output is correct
42 Correct 299 ms 111776 KB Output is correct
43 Correct 452 ms 122144 KB Output is correct
44 Correct 477 ms 128552 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 128552 KB Output is correct
2 Correct 2 ms 128552 KB Output is correct
3 Correct 2 ms 128552 KB Output is correct
4 Correct 3 ms 128552 KB Output is correct
5 Correct 3 ms 128552 KB Output is correct
6 Correct 3 ms 128552 KB Output is correct
7 Correct 3 ms 128552 KB Output is correct
8 Correct 2 ms 128552 KB Output is correct
9 Correct 3 ms 128552 KB Output is correct
10 Correct 3 ms 128552 KB Output is correct
11 Correct 3 ms 128552 KB Output is correct
12 Correct 4 ms 128552 KB Output is correct
13 Correct 2 ms 128552 KB Output is correct
14 Correct 3 ms 128552 KB Output is correct
15 Correct 3 ms 128552 KB Output is correct
16 Correct 3 ms 128552 KB Output is correct
17 Correct 3 ms 128552 KB Output is correct
18 Correct 2 ms 128552 KB Output is correct
19 Correct 3 ms 128552 KB Output is correct
20 Correct 4 ms 128552 KB Output is correct
21 Correct 4 ms 128552 KB Output is correct
22 Correct 4 ms 128552 KB Output is correct
23 Correct 5 ms 128552 KB Output is correct
24 Correct 4 ms 128552 KB Output is correct
25 Correct 5 ms 128552 KB Output is correct
26 Correct 5 ms 128552 KB Output is correct
27 Correct 6 ms 128552 KB Output is correct
28 Correct 5 ms 128552 KB Output is correct
29 Correct 4 ms 128552 KB Output is correct
30 Correct 4 ms 128552 KB Output is correct
31 Correct 6 ms 128552 KB Output is correct
32 Correct 7 ms 128552 KB Output is correct
33 Correct 882 ms 133756 KB Output is correct
34 Correct 713 ms 146288 KB Output is correct
35 Correct 696 ms 150108 KB Output is correct
36 Correct 808 ms 157828 KB Output is correct
37 Correct 256 ms 157828 KB Output is correct
38 Correct 255 ms 157828 KB Output is correct
39 Correct 457 ms 175576 KB Output is correct
40 Correct 465 ms 186500 KB Output is correct
41 Correct 274 ms 186500 KB Output is correct
42 Correct 326 ms 186500 KB Output is correct
43 Correct 232 ms 186500 KB Output is correct
44 Correct 443 ms 199536 KB Output is correct
45 Correct 247 ms 199536 KB Output is correct
46 Correct 304 ms 199536 KB Output is correct
47 Correct 492 ms 210040 KB Output is correct
48 Correct 421 ms 216244 KB Output is correct
49 Correct 396 ms 216244 KB Output is correct
50 Correct 482 ms 216244 KB Output is correct
51 Correct 723 ms 239220 KB Output is correct
52 Correct 643 ms 250612 KB Output is correct
53 Correct 833 ms 250612 KB Output is correct
54 Correct 568 ms 250612 KB Output is correct
55 Correct 324 ms 250612 KB Output is correct
56 Correct 564 ms 267720 KB Output is correct
57 Correct 477 ms 267720 KB Output is correct
58 Correct 652 ms 267720 KB Output is correct
59 Correct 438 ms 279360 KB Output is correct