oj.uz

Submission #81926

# Submission time Handle Problem Language Result Execution time Memory
81926 2018-10-27T20:00:17 Z GioChkhaidze Horses (IOI15_horses) C++14
100 / 100
 1353 ms 266544 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

#define Tree int h,int l,int r
#define left 2*h,l,(l+r)/2
#define right 2*h+1,(l+r)/2+1,r
#define Pb push_back
#define F first
#define S second

int Inf=1000000008,Mod=1000000007;
int P,n,x[500002],y[500002],ANS;
int Ind,Z;
int v[3000002];
pair < int , int > vy[3000002];
set < int > st;
set < int > :: iterator it;
vector < int > V;
pair < int , int > K;
int L,R;

void Update(Tree)
{
	if (l>L || r<L) return ;
	if (L==l && r==L) { v[h]=R%Mod; return ; }
	
	Update(left);
	Update(right);
	
	v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
}
int Get(Tree)
{
	if (L>r || l>R) return 1;
	if (L<=l && r<=R) return v[h];
	
	return (1LL*Get(left)*Get(right))%Mod;
}
void Upy(Tree)
{
	if (l>L || r<L) return ;
	if (L==l && r==L) { vy[h].F=R; vy[h].S=L; return ; }
	
	Upy(left);
	Upy(right);
	
	if (vy[2*h].F>vy[2*h+1].F) vy[h]=vy[2*h];
						  else vy[h]=vy[2*h+1];
}

pair < int , int > Gety(Tree)
{
	if (L>r || l>R) return make_pair(0,0);
	if (L<=l && r<=R) return make_pair(vy[h].F,vy[h].S);
	
	pair < int , int > X1=Gety(left);
	pair < int , int > X2=Gety(right);
	
	if (X1.F>X2.F) return X1;
		return X2;
}

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++)
	{
		L=i; R=x[i];
		Update(1,1,n);
		if (x[i]>1) st.insert(i);
	}
	
	for (int i=1; i<=n; i++)
	{
		L=i; R=y[i];
		Upy(1,1,n);
	}
	
	Ind=1;
	P=1;
		
	for (int j=2; j<=n; j++)
	{
		if (1LL*P*x[j]<Inf) P*=x[j];
				       else P=Inf;
				   
		if (y[Ind]<1LL*P*y[j]) P=1,Ind=j;	
	}
	
	L=1; R=Ind;
	
	ANS=(1LL*Get(1,1,n)*y[Ind])%Mod;

	return ANS;
}

int Ann()
{
	it=st.end();
	V.clear();
			
	Z=0;	
			
	while (it!=st.begin())
	{
		Z++;
		it--;
		V.Pb((*it));
		if (Z>35) break;
	}
		
	if (!V.size() || V[V.size()-1]!=1) V.Pb(1);	
	reverse(V.begin(),V.end());
	if (!V.size() || V[V.size()-1]!=n) V.Pb(n);		
		
	Ind=1;
	P=1;
		
	for (int i=0; i<V.size(); i++)
	{
		if (1LL*P*x[V[i]]<Inf) P*=x[V[i]];
				      	  else P=Inf;
				   
		if (y[Ind]<1LL*P*y[V[i]]) P=1,Ind=V[i];
				
		if (i==V.size()-1) continue;
		
		L=V[i]+1; R=V[i+1]-1;	
				
		K=Gety(1,1,n);
				
		if (y[Ind]<1LL*P*K.F) P=1,Ind=K.S;
	}
			
	L=1; R=Ind;		
				
	ANS=(1LL*Get(1,1,n)*y[Ind])%Mod;
	
	return ANS;
}

int updateX(int pos, int val) {	
	
	pos++;
	
	L=pos; R=val;

	if (x[pos]==1 && val>1) st.insert(pos);
			else
	if (x[pos]>1 && val==1) st.erase(st.find(pos));
			
	x[pos]=val;
		
	Update(1,1,n);
			
	return Ann();
}

int updateY(int pos, int val) {
	
	pos++;
	
	L=pos; R=val;
	
	y[pos]=val;
	Upy(1,1,n);
			
	return Ann();
}

Compilation message

horses.cpp: In function 'void Update(int, int, int)':
horses.cpp:31:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
       ~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int Get(int, int, int)':
horses.cpp:38:35: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (1LL*Get(left)*Get(right))%Mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:29: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  ANS=(1LL*Get(1,1,n)*y[Ind])%Mod;
      ~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int Ann()':
horses.cpp:124:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<V.size(); i++)
                ~^~~~~~~~~
horses.cpp:131:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i==V.size()-1) continue;
       ~^~~~~~~~~~~~
horses.cpp:142:29: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  ANS=(1LL*Get(1,1,n)*y[Ind])%Mod;
      ~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 2 ms 464 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 2 ms 592 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 2 ms 592 KB Output is correct
15 Correct 2 ms 620 KB Output is correct
16 Correct 2 ms 636 KB Output is correct
17 Correct 2 ms 636 KB Output is correct
18 Correct 2 ms 636 KB Output is correct
19 Correct 2 ms 636 KB Output is correct
20 Correct 2 ms 636 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1190 ms 45784 KB Output is correct
2 Correct 1301 ms 45784 KB Output is correct
3 Correct 1234 ms 49360 KB Output is correct
4 Correct 1323 ms 57092 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 57092 KB Output is correct
2 Correct 2 ms 57092 KB Output is correct
3 Correct 2 ms 57092 KB Output is correct
4 Correct 2 ms 57092 KB Output is correct
5 Correct 2 ms 57092 KB Output is correct
6 Correct 2 ms 57092 KB Output is correct
7 Correct 2 ms 57092 KB Output is correct
8 Correct 2 ms 57092 KB Output is correct
9 Correct 2 ms 57092 KB Output is correct
10 Correct 2 ms 57092 KB Output is correct
11 Correct 2 ms 57092 KB Output is correct
12 Correct 2 ms 57092 KB Output is correct
13 Correct 2 ms 57092 KB Output is correct
14 Correct 2 ms 57092 KB Output is correct
15 Correct 2 ms 57092 KB Output is correct
16 Correct 2 ms 57092 KB Output is correct
17 Correct 2 ms 57092 KB Output is correct
18 Correct 2 ms 57092 KB Output is correct
19 Correct 2 ms 57092 KB Output is correct
20 Correct 2 ms 57092 KB Output is correct
21 Correct 2 ms 57092 KB Output is correct
22 Correct 2 ms 57092 KB Output is correct
23 Correct 7 ms 57092 KB Output is correct
24 Correct 6 ms 57092 KB Output is correct
25 Correct 6 ms 57092 KB Output is correct
26 Correct 6 ms 57092 KB Output is correct
27 Correct 6 ms 57092 KB Output is correct
28 Correct 6 ms 57092 KB Output is correct
29 Correct 4 ms 57092 KB Output is correct
30 Correct 6 ms 57092 KB Output is correct
31 Correct 4 ms 57092 KB Output is correct
32 Correct 6 ms 57092 KB Output is correct
33 Correct 492 ms 57092 KB Output is correct
34 Correct 473 ms 57092 KB Output is correct
35 Correct 674 ms 75256 KB Output is correct
36 Correct 679 ms 85916 KB Output is correct
37 Correct 465 ms 85916 KB Output is correct
38 Correct 567 ms 85916 KB Output is correct
39 Correct 406 ms 85916 KB Output is correct
40 Correct 661 ms 99036 KB Output is correct
41 Correct 417 ms 99036 KB Output is correct
42 Correct 442 ms 99036 KB Output is correct
43 Correct 589 ms 109400 KB Output is correct
44 Correct 607 ms 115860 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 115860 KB Output is correct
2 Correct 2 ms 115860 KB Output is correct
3 Correct 2 ms 115860 KB Output is correct
4 Correct 2 ms 115860 KB Output is correct
5 Correct 2 ms 115860 KB Output is correct
6 Correct 2 ms 115860 KB Output is correct
7 Correct 2 ms 115860 KB Output is correct
8 Correct 2 ms 115860 KB Output is correct
9 Correct 2 ms 115860 KB Output is correct
10 Correct 2 ms 115860 KB Output is correct
11 Correct 2 ms 115860 KB Output is correct
12 Correct 2 ms 115860 KB Output is correct
13 Correct 2 ms 115860 KB Output is correct
14 Correct 2 ms 115860 KB Output is correct
15 Correct 2 ms 115860 KB Output is correct
16 Correct 2 ms 115860 KB Output is correct
17 Correct 2 ms 115860 KB Output is correct
18 Correct 2 ms 115860 KB Output is correct
19 Correct 2 ms 115860 KB Output is correct
20 Correct 2 ms 115860 KB Output is correct
21 Correct 2 ms 115860 KB Output is correct
22 Correct 2 ms 115860 KB Output is correct
23 Correct 7 ms 115860 KB Output is correct
24 Correct 6 ms 115860 KB Output is correct
25 Correct 6 ms 115860 KB Output is correct
26 Correct 6 ms 115860 KB Output is correct
27 Correct 6 ms 115860 KB Output is correct
28 Correct 8 ms 115860 KB Output is correct
29 Correct 3 ms 115860 KB Output is correct
30 Correct 7 ms 115860 KB Output is correct
31 Correct 5 ms 115860 KB Output is correct
32 Correct 5 ms 115860 KB Output is correct
33 Correct 1214 ms 121060 KB Output is correct
34 Correct 1296 ms 133520 KB Output is correct
35 Correct 1247 ms 137232 KB Output is correct
36 Correct 1322 ms 144928 KB Output is correct
37 Correct 502 ms 144928 KB Output is correct
38 Correct 476 ms 144928 KB Output is correct
39 Correct 671 ms 162688 KB Output is correct
40 Correct 695 ms 173736 KB Output is correct
41 Correct 476 ms 173736 KB Output is correct
42 Correct 564 ms 173736 KB Output is correct
43 Correct 400 ms 173736 KB Output is correct
44 Correct 673 ms 186800 KB Output is correct
45 Correct 423 ms 186800 KB Output is correct
46 Correct 439 ms 186800 KB Output is correct
47 Correct 598 ms 197068 KB Output is correct
48 Correct 600 ms 203748 KB Output is correct
49 Correct 1257 ms 203748 KB Output is correct
50 Correct 1085 ms 203748 KB Output is correct
51 Correct 1274 ms 226416 KB Output is correct
52 Correct 1247 ms 237824 KB Output is correct
53 Correct 1244 ms 237824 KB Output is correct
54 Correct 1271 ms 237824 KB Output is correct
55 Correct 588 ms 237824 KB Output is correct
56 Correct 1353 ms 254944 KB Output is correct
57 Correct 768 ms 254944 KB Output is correct
58 Correct 1026 ms 254944 KB Output is correct
59 Correct 610 ms 266544 KB Output is correct