답안 #71552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71552	2018-08-25T06:42:27 Z	Sa1378	말 (IOI15_horses)	C++17	100 / 100	979 ms	279360 KB

horses

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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