Submission #74023

#	Time	Username	Problem	Language	Result	Execution time	Memory
74023		aleksam	Horses (IOI15_horses)	C++14	34 / 100	1589 ms	42668 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define MAX_N 500000
#define MOD 1000000007
#define INF 1000000000
#define debug 0
using namespace std;

int segtree[4*MAX_N], N;
long long X[MAX_N], Y[MAX_N];
long long partX[4*MAX_N];

struct classcomp {
  bool operator() (const int& lhs, const int& rhs) const
  {return lhs>rhs;}
};

set<int, classcomp> S;//Skup indexa na kojima X[i]>1

int rmq(int ql, int qr){//Vraca index!!!
	//printf("rmq(%d, %d)\n", ql, qr);
	int max=0, indmax=-1;
	for(int i=ql; i<qr; ++i){
		if(Y[i]>max){
			max=Y[i];
			indmax=i;
		}
	}
	return indmax;
	//return query(ql, qr, 0, N, 0);
}

int partXX(int pos){
	long long ret=1;
	for(int i=0; i<pos+1; ++i){
		ret*=X[i];
		if(ret>MOD)ret%=MOD;
	}
	return ret;
	//return partquery(0, pos+1, 0, N, 0);
}


vector<int> big;//Indexi svih X-eva koji su veci od 1
int num_big=0;

int solve(){
	big.clear();//Moze brze
	long long pi=1;
	
	for(auto i:S){
		pi*=X[i];
		big.push_back(i);
		if(pi>INF)break;
	}
	if(pi<INF)big.push_back(0);
	reverse(big.begin(), big.end());
	/*if(pi<INF){
		big.clear();
		big.push_back(0);
		for(auto i:S){
			big.push_back(i);
		}
	}*/
	pi=1;
	int d=big.size();
	if(debug){
		for(int i=0; i<d; ++i)printf("%d ", big[i]);
		printf("\n");
	}
	long long totmax=0, indmax=-1;
	for(int i=0; i<d; ++i){
		long long maxy;
		if(i!=d-1){
			maxy=rmq(big[i], big[i+1]);
		}
		else {
			maxy=rmq(big[i], N);
			//printf("ovde\n");
		}
		if(debug){printf("Iteracija i=%d, big[i]=%d, maxy=%d, pi=%d\n", i, big[i], maxy, pi);}
		if(i!=0)pi*=X[big[i]];
		if((long long)Y[maxy]*pi>totmax){
			totmax=(long long)Y[maxy]*pi;
			indmax=maxy;
		}
		
	}
	if(debug){
		printf("totmax=%d, indmax=%d\n", totmax, indmax);
		printf("partXX(indmax)=%d\n", partXX(indmax));
	}
	long long res=(long long)Y[indmax]*partXX(indmax);
	return res%MOD;
}

int init(int n, int x[], int y[]) {
	N=n;
	for(int i=0; i<N; ++i){
		X[i]=x[i];
		Y[i]=y[i];
		if(X[i]>1){
			S.insert(i);
		}
	}
	//maketree(0, N, 0);
	if(debug){
		for(int i=0; i<4*N; ++i){
			printf("%*d ", 3, i);
		}
		printf("\n");
		for(int i=0; i<4*N; ++i){	
			printf("%*d ", 3, segtree[i]);
		}
		printf("\n");
		for(int i=0; i<4*N; ++i){
			printf("%*d ", 3, partX[i]);
		}
		printf("\n");
	}
	
	return solve();
}

int updateX(int pos, int val) {
	if(X[pos]==1 && val>1){
		S.insert(pos);
		X[pos]=val;
		//updatepart(0, N, 0, pos);
	}
	else if(X[pos]>1 && val==1){
		S.erase(pos);
		X[pos]=1;
		//updatepart(0, N, 0, pos);
	}
	else if(X[pos]>1 && val>1){
		X[pos]=val;
		//updatepart(0, N, 0, pos);
	}
	return solve();
}

int updateY(int pos, int val) {
	Y[pos]=val;
	//updatetree(0, N, 0, pos);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int rmq(int, int)':
horses.cpp:25:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    max=Y[i];
        ~~~^
horses.cpp: In function 'int partXX(int)':
horses.cpp:39:9: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return ret;
         ^~~
horses.cpp: In function 'int solve()':
horses.cpp:66:16: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int d=big.size();
        ~~~~~~~~^~
horses.cpp:81:86: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   if(debug){printf("Iteracija i=%d, big[i]=%d, maxy=%d, pi=%d\n", i, big[i], maxy, pi);}
                                                                                      ^
horses.cpp:81:86: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
horses.cpp:90:50: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   printf("totmax=%d, indmax=%d\n", totmax, indmax);
                                                  ^
horses.cpp:90:50: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
horses.cpp:91:46: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   printf("partXX(indmax)=%d\n", partXX(indmax));
                                              ^
horses.cpp:93:50: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  long long res=(long long)Y[indmax]*partXX(indmax);
                                                  ^
horses.cpp:94:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return res%MOD;
            ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:117:30: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
    printf("%*d ", 3, partX[i]);
                      ~~~~~~~~^

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23