oj.uz

Submission #868070

# Submission time Handle Problem Language Result Execution time Memory
868070 2023-10-30T11:22:46 Z waldi Horses (IOI15_horses) C++17
17 / 100
 1500 ms 12124 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define debug(a) cerr << #a << ": " << a << "\n";
#define maxc 1000000000ll
#define ssize(x) (int(x.size()))
#define mod 1000000007ll
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;



struct prz_ilo{
	int N;
	vector<ll> drz;
	void inicjalizuj(vector<ll> vec){
		int n = ssize(vec);
		for(N = 1; N < n;) N <<= 1;
		drz.resize(N<<1, 1ll);
		REP(i, n) drz[N+i] = vec[i];
		for(int i = N; --i;) drz[i] = (drz[i<<1]*drz[i<<1|1])%mod;
	}
	ll wart(int poz){
		return drz[N+poz];
	}
	void ustaw(int poz, ll wart){
		for(poz+=N, drz[poz]=wart; poz>>=1;) drz[poz] = (drz[poz<<1]*drz[poz<<1|1])%mod;
	}
	ll ilo(int p, int k){
		ll ret = 1ll;
		for(p+=N, k+=N+1; p<k; p>>=1, k>>=1){
			if(p&1) ret = (ret*drz[p++])%mod;
			if(k&1) ret = (ret*drz[--k])%mod;
		}
		return ret;
	}
} prz_ilo;// na ciagu x



struct prz_maks{
	int N;
	vector<ll> drz;
	void inicjalizuj(vector<ll> vec){
		int n = ssize(vec);
		for(N = 1; N < n;) N <<= 1;
		drz.resize(N<<1, 0);
		REP(i, n) drz[N+i] = vec[i];
		for(int i = N; --i;) drz[i] = max(drz[i<<1], drz[i<<1|1]);
	}
	ll wart(int poz){
		return drz[N+poz];
	}
	void ustaw(int poz, ll wart){
		for(poz+=N, drz[poz]=wart; poz>>=1;) drz[poz] = max(drz[poz<<1], drz[poz<<1|1]);
	}
	ll maks(int p, int k){
		ll ret = 0ll;
		for(p+=N, k+=N+1; p<k; p>>=1, k>>=1){
			if(p&1) ret = max(ret, drz[p++]);
			if(k&1) ret = max(ret, drz[--k]);
		}
		return ret;
	}
} prz_maks;// na ciagu y



int n;
set<int> nie1;// pozycje nie1 w ciagu x, ale pozycja 0 zawsze jest
int wynik(){
	ll wyn = -1ll, musze = -1ll;
	for(auto it = prev(nie1.end()); 1; it = prev(it)){
		if(musze > maxc) break;
		ll maks = prz_maks.maks(*it, n-1);
		if(maks > musze) wyn = (prz_ilo.ilo(0, *it)*maks)%mod, musze = maks;
		musze *= prz_maks.wart(*it);
		if(it == nie1.begin()) break;
	}
	return wyn;
}



int init(int nn, int xint[], int yint[]){
	n = nn;
	vector<ll> x(n), y(n);
	REP(i, n) x[i] = xint[i], y[i] = yint[i];
	
	ll wyn = 0ll;
	REP(i, n){
		ll tmp = y[i];
		FOR(j, 0, i) tmp *= x[j];
		wyn = max(wyn, tmp);
	}
	return wyn;
	
	prz_ilo.inicjalizuj(x);
	prz_maks.inicjalizuj(y);
	vector<int> vecnie1;
	REP(i, n) if(!i || x[i] > 1ll) vecnie1.emplace_back(i);
	nie1 = set<int>(all(vecnie1));
	
	return wynik();
}



int updateX(int poz, int wart){	
	prz_ilo.ustaw(poz, wart);
	if(!poz || wart > 1) nie1.emplace(poz);
	else nie1.erase(poz);
	return wynik();
}



int updateY(int poz, int wart){
	prz_maks.ustaw(poz, wart);
	return wynik();
}

Compilation message

horses.cpp: In function 'int wynik()':
horses.cpp:82:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   82 |  return wyn;
      |         ^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:98:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   98 |  return wyn;
      |         ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 436 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Runtime error 1 ms 432 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1557 ms 12124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 440 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Runtime error 1 ms 348 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Runtime error 0 ms 348 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -