oj.uz

Submission #571871

# Submission time Handle Problem Language Result Execution time Memory
571871 2022-06-03T02:21:44 Z kwongweng Horses (IOI15_horses) C++17
17 / 100
 1500 ms 27784 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef long long ll;
typedef long double ld;

#define FOR(i,a,b) for(int i = a; i < b; i++)
#define ROF(i,a,b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back

ll MOD = 1000000007;

ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}

vector<ll> x, y;
int n;

// range addition and maximum
struct segtree{
	vector<pair<double,int>> mx;
	int sz;
	void init(int m){
		sz = m;
		mx.assign(4*m, {0,-1});
		ini(1,0,sz-1);
	}
	void ini(int v, int tl, int tr){
		if (tl == tr){
			mx[tl].se = tl;
			return;
		}
		int tm = (tl+tr)/2;
		ini(2*v, tl, tm);
		ini(2*v+1, tm+1, tr);
	}

	void update(int v, int tl, int tr, int l, int r, double val){
		if (tl == l || tr == r){
			mx[v].fi += val;
			return;
		}
		if (l > r) return;
		int tm = (tl + tr)/2;
		update(2*v, tl, tm, l, min(r,tm), val);
		update(2*v+1, tm+1, tr, max(l,tm+1), r, val);
		if (mx[2*v].fi + 1e-7 > mx[2*v+1].fi){
			mx[v] = mx[2*v];
		}else{
			mx[v] = mx[2*v+1];
		}
	}
	void update(int l, int r, double val){
		update(1,0,sz-1,l,r,val);
	}
	int get(){
		return mx[1].se;
	}
} st;

vector<ld> a, b;

int init(int N, int X[], int Y[]) {
	n = N;
	FOR(i,0,n){
		x.pb(X[i]);
		y.pb(Y[i]);
	}
	a.pb(log(x[0])); b.pb(log(y[0]));
	FOR(i,1,n){
		a.pb(log(x[i])+a[i-1]);
		b.pb(log(y[i]));
	}
	ld mx = a[0]+b[0];
	int ind = 0;
	FOR(i,1,n){
		if (a[i]+b[i]+1e-9 > mx){
			mx = a[i]+b[i];
			ind = i;
		}
	}
	ll ans = y[ind];
	FOR(i,0,ind+1){
		ans *= x[i];
		ans %= MOD;
	}
	return ans;
	st.init(N); 
	FOR(i,0,N){
		st.update(i,n-1,log(X[i]));
		st.update(i,i,log(Y[i]));
	}
	cout << st.mx[1].fi << " " << st.mx[1].se << '\n';
	return st.get();
}

int updateX(int pos, int val) {	
	FOR(i,pos,n){
		a[i] += log(val) - log(a[pos]);
	}
	x[pos] = val;
	ld mx = a[0]+b[0];
	int ind = 0;
	FOR(i,1,n){
		if (a[i]+b[i]+1e-9 > mx){
			mx = a[i]+b[i];
			ind = i;
		}
	}
	ll ans = y[ind];
	FOR(i,0,ind+1){
		ans *= x[i];
		ans %= MOD;
	}
	return ans;
	st.update(pos,n-1,log(val)-log(x[pos]));
	x[pos] = val;
	cout << st.mx[1].fi << " " << st.mx[1].se << '\n';
	return st.get();
}

int updateY(int pos, int val) {
	y[pos] = val;
	b[pos] = log(val);
	ld mx = a[0]+b[0];
	int ind = 0;
	FOR(i,1,n){
		if (a[i]+b[i]+1e-9 > mx){
			mx = a[i]+b[i];
			ind = i;
		}
	}
	ll ans = y[ind];
	FOR(i,0,ind+1){
		ans *= x[i];
		ans %= MOD;
	}
	return ans;
	st.update(pos,pos,log(val)-log(y[pos]));
	y[pos] = val;
	cout << st.mx[1].fi << " " << st.mx[1].se << '\n';
	return st.get();
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:100:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  100 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:128:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:151:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  151 |  return ans;
      |         ^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Incorrect 14 ms 368 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 292 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Incorrect 16 ms 340 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Incorrect 14 ms 340 KB Output isn't correct
24 Halted 0 ms 0 KB -