Submission #74039

#	Time	Username	Problem	Language	Result	Execution time	Memory
74039		aleksam	Horses (IOI15_horses)	C++14	54 / 100	1576 ms	49336 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 partXX(int a);
void printtree(){
	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");
	}
}

void maketree(int l, int r, int v){
	if(l+1>=r){
		if(l==r-1){
			segtree[v]=l;
			partX[v]=X[l];
			return;
		}
		/*segtree[v]=-1;
		partX[v]=1;*/
		assert(0);
		return;
	}
	int mid=(l+r)/2;
	maketree(l, mid, 2*v+1);
	maketree(mid, r, 2*v+2);
	partX[v]=partX[2*v+1]*partX[2*v+2];
	partX[v]%=MOD;
	if(segtree[2*v+1]==-1){
		segtree[v]=segtree[2*v+2];
		return;
	}
	if(segtree[2*v+2]==-1){
		segtree[v]=segtree[2*v+1];
		return;
	}
	segtree[v]=Y[segtree[2*v+1]]>Y[segtree[2*v+2]]?segtree[2*v+1]:segtree[2*v+2];
	return;
}

int query(int ql, int qr, int l, int r, int v){
	//if(debug)printf("rmq(%d, %d, %d, %d)\n", ql, qr, l, r);
	if(ql>=r || qr<=l){
		return -1;
	}
	if(ql<=l  && r<=qr){
		return segtree[v];
	}
	int q1, q2;
	q1=query(ql, qr, l, (l+r)/2, 2*v+1);
	q2=query(ql, qr, (l+r)/2, r, 2*v+2);
	if(q1==-1)return q2;
	if(q2==-1)return q1;
	return Y[q1]>Y[q2]?q1:q2;
}

int partquery(int ql, int qr, int l, int r, int v){
	if(ql>=r || qr<=l){
		return 1;
	}
	if(ql<=l  && r<=qr){
		return partX[v];
	}
	long long q1, q2;
	q1=partquery(ql, qr, l, (l+r)/2, 2*v+1);
	q2=partquery(ql, qr, (l+r)/2, r, 2*v+2);
	return (q1*q2)%MOD;
}

void updatetree(int l, int r, int v, int x){
	if(l+1>=r){
		return;
	}
	if(l<=x && x<r){
		updatetree(l, (l+r)/2, 2*v+1, x);
		updatetree((l+r)/2, r, 2*v+2, x);
		if(segtree[2*v+1]==-1){
			segtree[v]=segtree[2*v+2];
			return;
		}
		if(segtree[2*v+2]==-1){
			segtree[v]=segtree[2*v+1];
			return;
		}
		segtree[v]=Y[segtree[2*v+1]]>Y[segtree[2*v+2]]?segtree[2*v+1]:segtree[2*v+2];
	}
}

void updatepart(int l, int r, int v, int x){
	//printf("updatepart(%d, %d, %d);\n", l, r, x);
	if(l+1>=r){
		if(l==x)partX[v]=X[x];
		return;
	}
	if(l<=x && x<r){
		updatepart(l, (l+r)/2, 2*v+1, x);
		updatepart((l+r)/2, r, 2*v+2, x);
		partX[v]=(partX[2*v+1]*partX[2*v+2])%MOD;
	}
}

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);
}

int buff[50];//Indexi svih X-eva koji su veci od 1
int num_big=0;

int solve(){
	//Moze brze
	long long pi=1;
	int ind=0;
	for(auto i:S){
		pi*=X[i];
		buff[ind++]=i;
		if(pi>INF)break;
	}
	if(pi<INF)buff[ind++]=0;
	reverse(buff, buff+ind);
	/*if(pi<INF){
		big.clear();
		big.push_back(0);
		for(auto i:S){
			big.push_back(i);
		}
	}*/
	pi=1;
	int *big=buff;
	int d=ind;
	if(debug){
		for(int i=0; i<d; ++i)printf("%d ", buff[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);
	printtree();
	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);
	}
	printtree();
	return solve();
}

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

Compilation message (stderr)

horses.cpp: In function 'void printtree()':
horses.cpp:31:30: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
    printf("%*d ", 3, partX[i]);
                      ~~~~~~~~^
horses.cpp: In function 'int partquery(int, int, int, int, int)':
horses.cpp:87:17: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   return partX[v];
          ~~~~~~~^
horses.cpp:92:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (q1*q2)%MOD;
                ^
horses.cpp: In function 'int rmq(int, int)':
horses.cpp:132:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
    max=Y[i];
        ~~~^
horses.cpp: In function 'int solve()':
horses.cpp:200: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:201:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return res%MOD;
            ^

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