oj.uz

Submission #332560

# Submission time Handle Problem Language Result Execution time Memory
332560 2020-12-02T21:33:37 Z zggf Horses (IOI15_horses) C++14
0 / 100
 256 ms 53100 KB 
#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

set<long long, greater<long long>> mp;
vector<long long> ceny, konie, treeMax, treePref;
long long treeSize;
long long mod = 1e9+7;
long long pref = 1;

long long pot(long long a, long long b){
	if(b==0) return 1;
	if(b%2==0){
		long long cur = pot(a, b/2);
		return (cur*cur)%mod;	
	}else return (a*pot(a, b-1))%mod;
}

long long pot2(long long x){
	long long tmp = 1;
	while(x){
		x/=2;
		tmp*=2;	
	}
	return tmp;
}
void dziel(long long a, long long b){
	a = (a*pot(b, mod-2))%mod;	
}


long long qurTreeMax(long long a, long long b){
	long long out = 0;
	a+=treeSize; b+=treeSize;
	out = max(treeMax[a], treeMax[b]);		
	while(a/2!=b/2){
		if(a%2==0) out = max(out, treeMax[a+1]);	
		if(b%2==1) out = max(out, treeMax[b-1]);
		a/=2; b/=2;
	}
	return out;
}

long long qurTreePref(long long a, long long b){
	long long out = 1;
	a+=treeSize; b+=treeSize;
	out = treePref[a];		
	if(a!=b) out*=treePref[b];
	out%=mod;
	while(a/2!=b/2){
		if(a%2==0) out = (out*treePref[a+1])%mod;	
		if(b%2==1) out = (out*treePref[b-1])%mod;
		a/=2; b/=2;
	}
	return out;
}
int qur(){
	vector<pair<long long, long long>> vec;
	if(mp.size()==0){
		return qurTreeMax(0, treeSize-1);	
	}
	auto it = mp.begin();		
	long long coc = 1;
	vector<long long> stck;
	while(it!=mp.end()&&coc<(long long)1e9){
		coc*=konie[*it];	
		stck.push_back(*it);
		it++;
	}
	reverse(stck.begin(), stck.end());
	coc = 1;
	long long wyn = treeMax[1];
	for(long long i = 0; i < (long long)stck.size(); i++){
		long long x = stck[i];
		coc*=konie[x];
		wyn = max(wyn, coc*qurTreeMax(x, (i==(long long)stck.size()-1)?x:(stck[i+1]-1)));
	}
	return (int)(wyn*((stck[0]==0)?1ll:qurTreePref(0, stck[0]-1)))%mod;
}

int init(int N, int X[], int Y[]) {
	ceny.resize(N);
	konie.resize(N);
	treeSize = pot2(N);
	treeMax.resize(treeSize*2+1);
	treePref.resize(treeSize*2+1);

	for(long long i = 0;i < N; i++){
		ceny[i] = Y[i];
		treeMax[i+treeSize] = ceny[i];
		treePref[i+treeSize] = X[i];
		konie[i] = X[i];	
		if(konie[i]>1) mp.insert(i);
	}

	for(int i = (int)treeSize-1; i>0; i--){
		treeMax[i] = max(treeMax[i*2], treeMax[i*2+1]);	
		treePref[i] = (treePref[i*2]*treePref[i*2+1])%mod;
	}
	return qur();
}
int updateX(int pos, int val) {	
	if(konie[pos]>1&&val==1) mp.erase(pos);
	if(konie[pos]==1&&val>1) mp.insert(pos);
	konie[pos] = val;
	pos+=(int)treeSize;
	treePref[pos] = val;
	pos/=2;
	while(pos){
		treePref[pos] = (treePref[pos*2]*treePref[pos*2+1])%mod;	
		pos/=2;
	}	
	return qur();
}

int updateY(int pos, int val) {
	ceny[pos] = val;
	pos+=(int)treeSize;
	treeMax[pos] = val;
	pos/=2;
	while(pos){
		treeMax[pos] = max(treeMax[pos*2], treeMax[pos*2+1]);	
		pos/=2;
	}
	return qur();
}

Compilation message

horses.cpp: In function 'int qur()':
horses.cpp:61:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   61 |   return qurTreeMax(0, treeSize-1);
      |          ~~~~~~~~~~^~~~~~~~~~~~~~~
horses.cpp:79:64: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |  return (int)(wyn*((stck[0]==0)?1ll:qurTreePref(0, stck[0]-1)))%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 0 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 256 ms 53100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -