Submission #426353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426353	2021-06-13T19:04:55 Z	LastRonin	Horses (IOI15_horses)	C++14	100 / 100	600 ms	143488 KB

horses

#include "horses.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define mp make_pair
#define double long double
using namespace std;

const ll N = 5e5 + 100;
const ll mod = 1e9 + 7;

ll n;
double x[N], y[N], pr[N];


struct seg {
	pair<double, int> t[4 * N];
	double u[4 * N];
	void push(ll v) {
		t[v].f += u[v];
		if(v * 2 + 1 < 4 * N)
			u[v * 2] += u[v],
			u[v * 2 + 1] += u[v];
		u[v] = 0;
	}
	void build(ll v = 1, ll l = 1, ll r = n) {
		if(l == r) {
			t[v].f = pr[l];
			t[v].s = l;
			return;
		}
		ll m = (l + r) >> 1ll;
		build(v * 2, l, m);
		build(v * 2 + 1, m + 1, r);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
	void upd(ll l, ll r, double z, ll v = 1, ll tl = 1, ll tr = n) {
		push(v);
		if(l > tr || tl > r)
			return;
		if(l <= tl && tr <= r) {
			u[v] += z;
			push(v);
			return;
		}
		ll m = (tl + tr) >> 1ll;
		upd(l, r, z, v * 2, tl, m);
		upd(l, r, z, v * 2 + 1, m + 1, tr);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
} rt;

struct seg1 {
	ll t[4 * N];
	void upd(ll p, ll z, ll v = 1, ll tl = 1, ll tr = n) {
		if(tl == tr) {
			t[v] = z;
			return;
		}
		ll m = (tl + tr) >> 1ll;
		if(p <= m)
			upd(p, z, v * 2, tl, m);
		else
			upd(p, z, v * 2 + 1, m + 1, tr);
		t[v] = t[v * 2] * t[v * 2 + 1] % mod;					
	}
	ll get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n) {
		if(l > tr || tl > r)
			return 1ll;
		if(l <= tl && tr <= r)
			return t[v];
		ll m = (tl + tr) >> 1ll;
		return get(l, r, v * 2, tl, m) * get(l, r, v * 2 + 1, m + 1, tr) % mod;
	}
} rt2;

int init(int p, int p2[], int p3[]) {
	n = p;
	for(int i = 1; i <= n; i++)
		x[i] = p2[i - 1], y[i] = p3[i - 1],
		rt2.upd(i, x[i]),
		pr[i] = pr[i - 1] + log(x[i]);
	for(int j = 1; j <= n; j++) {
		pr[j] = pr[j] + log(y[j]);
	}
	rt.build();
	ll z = rt.t[1].s;
	ll ans = rt2.get(1, z) * (ll)y[z] % mod;
	return ans;
}
  
int updateX(int pos, int val) {	
	pos++;
    double lst = x[pos];
	x[pos] = val;
	double za = log(x[pos]) - log(lst);
	rt.upd(pos, n, za);
	rt2.upd(pos, val);
	ll z = rt.t[1].s;
	ll ans = rt2.get(1, z) * (ll)y[z] % mod;
	return ans;
}
int updateY(int pos, int val) {
    pos++;
    double lst = y[pos];
    y[pos] = val;
    double za = log(y[pos]) - log(lst);
    rt.upd(pos, pos, za);
    ll z = rt.t[1].s;
    ll ans = rt2.get(1, z) * (ll)y[z] % mod; 
	return ans;
}

Compilation message

horses.cpp: In member function 'void seg::build(long long int, long long int, long long int)':
horses.cpp:30:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   30 |    t[v].s = l;
      |             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:82:17: warning: conversion from 'long double' to 'long long int' may change value [-Wfloat-conversion]
   82 |   rt2.upd(i, x[i]),
      |              ~~~^
horses.cpp:90:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   90 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:102:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:112:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  112 |  return ans;
      |         ^~~

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	62952 KB	Output is correct
2	Correct	26 ms	62904 KB	Output is correct
3	Correct	30 ms	62860 KB	Output is correct
4	Correct	27 ms	62916 KB	Output is correct
5	Correct	32 ms	62996 KB	Output is correct
6	Correct	34 ms	62912 KB	Output is correct
7	Correct	26 ms	62844 KB	Output is correct
8	Correct	27 ms	62896 KB	Output is correct
9	Correct	27 ms	62976 KB	Output is correct
10	Correct	27 ms	62888 KB	Output is correct
11	Correct	28 ms	62856 KB	Output is correct
12	Correct	26 ms	62924 KB	Output is correct
13	Correct	28 ms	62944 KB	Output is correct
14	Correct	27 ms	62828 KB	Output is correct
15	Correct	28 ms	62932 KB	Output is correct
16	Correct	29 ms	62892 KB	Output is correct
17	Correct	28 ms	62924 KB	Output is correct
18	Correct	29 ms	62916 KB	Output is correct
19	Correct	27 ms	62844 KB	Output is correct
20	Correct	29 ms	62936 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	62924 KB	Output is correct
2	Correct	33 ms	62916 KB	Output is correct
3	Correct	27 ms	62936 KB	Output is correct
4	Correct	31 ms	62928 KB	Output is correct
5	Correct	28 ms	62928 KB	Output is correct
6	Correct	33 ms	62888 KB	Output is correct
7	Correct	27 ms	62888 KB	Output is correct
8	Correct	30 ms	62928 KB	Output is correct
9	Correct	29 ms	62896 KB	Output is correct
10	Correct	29 ms	62872 KB	Output is correct
11	Correct	30 ms	62940 KB	Output is correct
12	Correct	28 ms	62852 KB	Output is correct
13	Correct	27 ms	62904 KB	Output is correct
14	Correct	29 ms	62876 KB	Output is correct
15	Correct	29 ms	62924 KB	Output is correct
16	Correct	29 ms	62936 KB	Output is correct
17	Correct	27 ms	62940 KB	Output is correct
18	Correct	29 ms	62900 KB	Output is correct
19	Correct	30 ms	62856 KB	Output is correct
20	Correct	28 ms	62932 KB	Output is correct
21	Correct	27 ms	62840 KB	Output is correct
22	Correct	36 ms	62900 KB	Output is correct
23	Correct	28 ms	63036 KB	Output is correct
24	Correct	30 ms	63108 KB	Output is correct
25	Correct	29 ms	63032 KB	Output is correct
26	Correct	31 ms	63052 KB	Output is correct
27	Correct	29 ms	63048 KB	Output is correct
28	Correct	30 ms	63060 KB	Output is correct
29	Correct	28 ms	63028 KB	Output is correct
30	Correct	32 ms	63052 KB	Output is correct
31	Correct	29 ms	63092 KB	Output is correct
32	Correct	34 ms	63044 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	375 ms	103348 KB	Output is correct
2	Correct	577 ms	143452 KB	Output is correct
3	Correct	556 ms	134520 KB	Output is correct
4	Correct	567 ms	138404 KB	Output is correct

Subtask #4

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	62924 KB	Output is correct
2	Correct	27 ms	62912 KB	Output is correct
3	Correct	28 ms	62860 KB	Output is correct
4	Correct	29 ms	62916 KB	Output is correct
5	Correct	31 ms	62872 KB	Output is correct
6	Correct	29 ms	62916 KB	Output is correct
7	Correct	28 ms	62952 KB	Output is correct
8	Correct	28 ms	62976 KB	Output is correct
9	Correct	27 ms	62892 KB	Output is correct
10	Correct	27 ms	62940 KB	Output is correct
11	Correct	27 ms	62880 KB	Output is correct
12	Correct	30 ms	62924 KB	Output is correct
13	Correct	29 ms	62860 KB	Output is correct
14	Correct	28 ms	62872 KB	Output is correct
15	Correct	28 ms	62972 KB	Output is correct
16	Correct	29 ms	62924 KB	Output is correct
17	Correct	30 ms	62932 KB	Output is correct
18	Correct	33 ms	62872 KB	Output is correct
19	Correct	29 ms	62924 KB	Output is correct
20	Correct	32 ms	62924 KB	Output is correct
21	Correct	29 ms	62916 KB	Output is correct
22	Correct	27 ms	62924 KB	Output is correct
23	Correct	29 ms	63084 KB	Output is correct
24	Correct	29 ms	63124 KB	Output is correct
25	Correct	30 ms	63096 KB	Output is correct
26	Correct	29 ms	63000 KB	Output is correct
27	Correct	29 ms	63052 KB	Output is correct
28	Correct	29 ms	63104 KB	Output is correct
29	Correct	31 ms	63052 KB	Output is correct
30	Correct	33 ms	63156 KB	Output is correct
31	Correct	29 ms	63172 KB	Output is correct
32	Correct	30 ms	63044 KB	Output is correct
33	Correct	272 ms	131080 KB	Output is correct
34	Correct	260 ms	131040 KB	Output is correct
35	Correct	254 ms	109484 KB	Output is correct
36	Correct	254 ms	109508 KB	Output is correct
37	Correct	280 ms	128948 KB	Output is correct
38	Correct	239 ms	102212 KB	Output is correct
39	Correct	220 ms	100832 KB	Output is correct
40	Correct	242 ms	105028 KB	Output is correct
41	Correct	219 ms	101844 KB	Output is correct
42	Correct	244 ms	100804 KB	Output is correct
43	Correct	230 ms	105124 KB	Output is correct
44	Correct	220 ms	105028 KB	Output is correct

Subtask #5

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	62880 KB	Output is correct
2	Correct	33 ms	62904 KB	Output is correct
3	Correct	27 ms	63052 KB	Output is correct
4	Correct	29 ms	62912 KB	Output is correct
5	Correct	33 ms	62948 KB	Output is correct
6	Correct	28 ms	62960 KB	Output is correct
7	Correct	28 ms	62876 KB	Output is correct
8	Correct	29 ms	62916 KB	Output is correct
9	Correct	29 ms	62928 KB	Output is correct
10	Correct	29 ms	62932 KB	Output is correct
11	Correct	33 ms	62848 KB	Output is correct
12	Correct	27 ms	62868 KB	Output is correct
13	Correct	31 ms	62900 KB	Output is correct
14	Correct	26 ms	62860 KB	Output is correct
15	Correct	27 ms	62924 KB	Output is correct
16	Correct	28 ms	62956 KB	Output is correct
17	Correct	27 ms	62924 KB	Output is correct
18	Correct	27 ms	62896 KB	Output is correct
19	Correct	28 ms	62924 KB	Output is correct
20	Correct	27 ms	62868 KB	Output is correct
21	Correct	28 ms	62924 KB	Output is correct
22	Correct	34 ms	62924 KB	Output is correct
23	Correct	34 ms	63004 KB	Output is correct
24	Correct	30 ms	63052 KB	Output is correct
25	Correct	28 ms	62996 KB	Output is correct
26	Correct	28 ms	63048 KB	Output is correct
27	Correct	30 ms	63016 KB	Output is correct
28	Correct	29 ms	63008 KB	Output is correct
29	Correct	35 ms	63008 KB	Output is correct
30	Correct	30 ms	63080 KB	Output is correct
31	Correct	29 ms	63060 KB	Output is correct
32	Correct	31 ms	63056 KB	Output is correct
33	Correct	385 ms	103388 KB	Output is correct
34	Correct	545 ms	143488 KB	Output is correct
35	Correct	546 ms	134724 KB	Output is correct
36	Correct	600 ms	138468 KB	Output is correct
37	Correct	273 ms	131320 KB	Output is correct
38	Correct	271 ms	130996 KB	Output is correct
39	Correct	271 ms	109556 KB	Output is correct
40	Correct	253 ms	109520 KB	Output is correct
41	Correct	258 ms	128908 KB	Output is correct
42	Correct	236 ms	102100 KB	Output is correct
43	Correct	230 ms	100732 KB	Output is correct
44	Correct	237 ms	105176 KB	Output is correct
45	Correct	220 ms	101872 KB	Output is correct
46	Correct	221 ms	100700 KB	Output is correct
47	Correct	223 ms	104996 KB	Output is correct
48	Correct	220 ms	104948 KB	Output is correct
49	Correct	552 ms	136004 KB	Output is correct
50	Correct	516 ms	135856 KB	Output is correct
51	Correct	423 ms	111484 KB	Output is correct
52	Correct	399 ms	110960 KB	Output is correct
53	Correct	511 ms	134312 KB	Output is correct
54	Correct	427 ms	108680 KB	Output is correct
55	Correct	366 ms	101856 KB	Output is correct
56	Correct	423 ms	111444 KB	Output is correct
57	Correct	367 ms	103492 KB	Output is correct
58	Correct	379 ms	102824 KB	Output is correct
59	Correct	220 ms	104928 KB	Output is correct