oj.uz

Submission #795460

# Submission time Handle Problem Language Result Execution time Memory
795460 2023-07-27T10:04:51 Z Ronin13 Horses (IOI15_horses) C++17
100 / 100
 180 ms 139248 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back

const int nmax = 1000001;
const ll mod = 1e9 + 7;
struct node{
	double sum, mx = 0;
	ll ans;
	ll x;
	node(){
		sum = mx = 0;
		ans = 1;
		x = 1;
	}

}t[4 * nmax];

ll x[nmax], y[nmax];

node merg(node a, node b){
	node c;
	c.sum = a.sum + b.sum;
	c.x = a.x * b.x % mod;
	if(a.mx > a.sum + b.mx){
		c.mx = a.mx;
		c.ans = a.ans;
	}
	else{
		c.mx = a.sum + b.mx;
		c.ans = b.ans * a.x % mod;
	}
	return c;
}

void build(int v, int l, int r){
	if(l == r){
		t[v].sum = log2(x[l]);
		t[v].mx = log2(x[l]) + log2(y[l]);
		t[v].ans = x[l] * y[l] % mod;
		t[v].x = x[l];
		return;
	}
	int m = (l + r) / 2;
	build(2 * v, l, m);
	build(2 * v+ 1, m + 1, r);
	t[v] = merg(t[2 * v], t[2 * v + 1]);
}

void update(int v, int l, int r, int pos, int val, int ind){
	if(l > pos || r < pos)
		return;
	if(l == r){
		if(ind == 0) x[l] = val;
		else y[l] = val;
		t[v].sum = log2(x[l]);
		t[v].mx = log2(x[l]) + log2(y[l]);
		t[v].ans = x[l] * y[l] % mod;
		t[v].x = x[l];
		return;
	}
	int m = (l + r) / 2;
	update(2 * v, l, m, pos, val, ind);
	update(2 * v+ 1, m + 1, r, pos, val, ind);
	t[v] = merg(t[2 * v], t[2 * v + 1]);
}
int n;
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];
	}
	build(1, 0, n - 1);
	return t[1].ans;
}

int updateX(int pos, int val) {	
	update(1, 0, n - 1, pos, val, 0);
	return t[1].ans;
}

int updateY(int pos, int val) {
	update(1, 0, n - 1, pos, val, 1);
	return t[1].ans;
}

Compilation message

horses.cpp: In function 'void build(int, int, int)':
horses.cpp:45:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   45 |   t[v].sum = log2(x[l]);
      |                   ~~~^
horses.cpp:46:21: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   46 |   t[v].mx = log2(x[l]) + log2(y[l]);
      |                  ~~~^
horses.cpp:46:34: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   46 |   t[v].mx = log2(x[l]) + log2(y[l]);
      |                               ~~~^
horses.cpp: In function 'void update(int, int, int, int, int, int)':
horses.cpp:63:22: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   63 |   t[v].sum = log2(x[l]);
      |                   ~~~^
horses.cpp:64:21: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   64 |   t[v].mx = log2(x[l]) + log2(y[l]);
      |                  ~~~^
horses.cpp:64:34: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   64 |   t[v].mx = log2(x[l]) + log2(y[l]);
      |                               ~~~^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:81:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |  return t[1].ans;
      |         ~~~~~^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:86:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |  return t[1].ans;
      |         ~~~~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:91:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  return t[1].ans;
      |         ~~~~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 125476 KB Output is correct
2 Correct 45 ms 125516 KB Output is correct
3 Correct 49 ms 125516 KB Output is correct
4 Correct 43 ms 125436 KB Output is correct
5 Correct 43 ms 125444 KB Output is correct
6 Correct 44 ms 125488 KB Output is correct
7 Correct 42 ms 125508 KB Output is correct
8 Correct 42 ms 125464 KB Output is correct
9 Correct 44 ms 125516 KB Output is correct
10 Correct 44 ms 125532 KB Output is correct
11 Correct 43 ms 125452 KB Output is correct
12 Correct 43 ms 125516 KB Output is correct
13 Correct 45 ms 125440 KB Output is correct
14 Correct 45 ms 125432 KB Output is correct
15 Correct 43 ms 125512 KB Output is correct
16 Correct 49 ms 125516 KB Output is correct
17 Correct 42 ms 125516 KB Output is correct
18 Correct 42 ms 125484 KB Output is correct
19 Correct 42 ms 125460 KB Output is correct
20 Correct 43 ms 125536 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125512 KB Output is correct
2 Correct 50 ms 125516 KB Output is correct
3 Correct 42 ms 125448 KB Output is correct
4 Correct 42 ms 125456 KB Output is correct
5 Correct 42 ms 125452 KB Output is correct
6 Correct 42 ms 125496 KB Output is correct
7 Correct 42 ms 125516 KB Output is correct
8 Correct 43 ms 125480 KB Output is correct
9 Correct 48 ms 125496 KB Output is correct
10 Correct 49 ms 125516 KB Output is correct
11 Correct 47 ms 125492 KB Output is correct
12 Correct 43 ms 125516 KB Output is correct
13 Correct 42 ms 125440 KB Output is correct
14 Correct 43 ms 125512 KB Output is correct
15 Correct 42 ms 125468 KB Output is correct
16 Correct 42 ms 125500 KB Output is correct
17 Correct 43 ms 125548 KB Output is correct
18 Correct 43 ms 125500 KB Output is correct
19 Correct 43 ms 125456 KB Output is correct
20 Correct 45 ms 125544 KB Output is correct
21 Correct 49 ms 125500 KB Output is correct
22 Correct 44 ms 125552 KB Output is correct
23 Correct 50 ms 125524 KB Output is correct
24 Correct 44 ms 125512 KB Output is correct
25 Correct 42 ms 125532 KB Output is correct
26 Correct 43 ms 125508 KB Output is correct
27 Correct 47 ms 125476 KB Output is correct
28 Correct 44 ms 125496 KB Output is correct
29 Correct 42 ms 125544 KB Output is correct
30 Correct 45 ms 125572 KB Output is correct
31 Correct 42 ms 125560 KB Output is correct
32 Correct 43 ms 125516 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 138196 KB Output is correct
2 Correct 172 ms 138208 KB Output is correct
3 Correct 133 ms 138256 KB Output is correct
4 Correct 164 ms 138288 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125552 KB Output is correct
2 Correct 46 ms 125524 KB Output is correct
3 Correct 49 ms 125464 KB Output is correct
4 Correct 44 ms 125448 KB Output is correct
5 Correct 43 ms 125508 KB Output is correct
6 Correct 42 ms 125432 KB Output is correct
7 Correct 45 ms 125480 KB Output is correct
8 Correct 48 ms 125492 KB Output is correct
9 Correct 45 ms 125468 KB Output is correct
10 Correct 43 ms 125516 KB Output is correct
11 Correct 42 ms 125496 KB Output is correct
12 Correct 42 ms 125436 KB Output is correct
13 Correct 43 ms 125536 KB Output is correct
14 Correct 43 ms 125520 KB Output is correct
15 Correct 43 ms 125420 KB Output is correct
16 Correct 42 ms 125416 KB Output is correct
17 Correct 50 ms 125616 KB Output is correct
18 Correct 50 ms 125528 KB Output is correct
19 Correct 44 ms 125432 KB Output is correct
20 Correct 51 ms 125428 KB Output is correct
21 Correct 44 ms 125436 KB Output is correct
22 Correct 43 ms 125428 KB Output is correct
23 Correct 43 ms 125580 KB Output is correct
24 Correct 43 ms 125552 KB Output is correct
25 Correct 43 ms 125548 KB Output is correct
26 Correct 45 ms 125488 KB Output is correct
27 Correct 49 ms 125580 KB Output is correct
28 Correct 47 ms 125576 KB Output is correct
29 Correct 49 ms 125520 KB Output is correct
30 Correct 42 ms 125540 KB Output is correct
31 Correct 43 ms 125572 KB Output is correct
32 Correct 42 ms 125484 KB Output is correct
33 Correct 81 ms 137296 KB Output is correct
34 Correct 86 ms 138744 KB Output is correct
35 Correct 108 ms 138576 KB Output is correct
36 Correct 113 ms 138620 KB Output is correct
37 Correct 76 ms 138536 KB Output is correct
38 Correct 85 ms 137964 KB Output is correct
39 Correct 67 ms 137968 KB Output is correct
40 Correct 84 ms 137996 KB Output is correct
41 Correct 64 ms 138040 KB Output is correct
42 Correct 66 ms 137968 KB Output is correct
43 Correct 90 ms 137932 KB Output is correct
44 Correct 89 ms 137852 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125476 KB Output is correct
2 Correct 43 ms 125460 KB Output is correct
3 Correct 42 ms 125428 KB Output is correct
4 Correct 42 ms 125500 KB Output is correct
5 Correct 42 ms 125528 KB Output is correct
6 Correct 43 ms 125464 KB Output is correct
7 Correct 46 ms 125480 KB Output is correct
8 Correct 42 ms 125540 KB Output is correct
9 Correct 42 ms 125444 KB Output is correct
10 Correct 45 ms 125548 KB Output is correct
11 Correct 43 ms 125428 KB Output is correct
12 Correct 43 ms 125556 KB Output is correct
13 Correct 47 ms 125492 KB Output is correct
14 Correct 48 ms 125520 KB Output is correct
15 Correct 43 ms 125516 KB Output is correct
16 Correct 50 ms 125596 KB Output is correct
17 Correct 42 ms 125480 KB Output is correct
18 Correct 43 ms 125540 KB Output is correct
19 Correct 47 ms 125516 KB Output is correct
20 Correct 53 ms 125504 KB Output is correct
21 Correct 44 ms 125460 KB Output is correct
22 Correct 43 ms 125524 KB Output is correct
23 Correct 45 ms 125492 KB Output is correct
24 Correct 50 ms 125496 KB Output is correct
25 Correct 48 ms 125532 KB Output is correct
26 Correct 44 ms 125488 KB Output is correct
27 Correct 44 ms 125528 KB Output is correct
28 Correct 44 ms 125528 KB Output is correct
29 Correct 43 ms 125544 KB Output is correct
30 Correct 46 ms 125572 KB Output is correct
31 Correct 48 ms 125536 KB Output is correct
32 Correct 50 ms 125492 KB Output is correct
33 Correct 113 ms 138476 KB Output is correct
34 Correct 180 ms 139176 KB Output is correct
35 Correct 145 ms 138996 KB Output is correct
36 Correct 160 ms 139248 KB Output is correct
37 Correct 89 ms 138176 KB Output is correct
38 Correct 92 ms 137848 KB Output is correct
39 Correct 108 ms 137744 KB Output is correct
40 Correct 123 ms 137784 KB Output is correct
41 Correct 72 ms 137464 KB Output is correct
42 Correct 77 ms 137420 KB Output is correct
43 Correct 66 ms 137416 KB Output is correct
44 Correct 92 ms 137432 KB Output is correct
45 Correct 64 ms 137420 KB Output is correct
46 Correct 73 ms 137452 KB Output is correct
47 Correct 86 ms 137408 KB Output is correct
48 Correct 95 ms 137392 KB Output is correct
49 Correct 162 ms 138364 KB Output is correct
50 Correct 143 ms 138372 KB Output is correct
51 Correct 133 ms 138360 KB Output is correct
52 Correct 150 ms 138316 KB Output is correct
53 Correct 147 ms 138380 KB Output is correct
54 Correct 127 ms 138312 KB Output is correct
55 Correct 93 ms 137640 KB Output is correct
56 Correct 115 ms 138408 KB Output is correct
57 Correct 92 ms 138312 KB Output is correct
58 Correct 105 ms 138440 KB Output is correct
59 Correct 98 ms 137420 KB Output is correct