oj.uz

Submission #795459

# Submission time Handle Problem Language Result Execution time Memory
795459 2023-07-27T10:04:03 Z Ronin13 Horses (IOI15_horses) C++17
34 / 100
 65 ms 66628 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 = 200001;
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 10 ms 25300 KB Output is correct
2 Correct 10 ms 25300 KB Output is correct
3 Correct 10 ms 25300 KB Output is correct
4 Correct 10 ms 25300 KB Output is correct
5 Correct 10 ms 25352 KB Output is correct
6 Correct 10 ms 25300 KB Output is correct
7 Correct 11 ms 25300 KB Output is correct
8 Correct 11 ms 25300 KB Output is correct
9 Correct 10 ms 25300 KB Output is correct
10 Correct 11 ms 25300 KB Output is correct
11 Correct 10 ms 25300 KB Output is correct
12 Correct 10 ms 25256 KB Output is correct
13 Correct 11 ms 25300 KB Output is correct
14 Correct 11 ms 25300 KB Output is correct
15 Correct 11 ms 25300 KB Output is correct
16 Correct 10 ms 25300 KB Output is correct
17 Correct 14 ms 25300 KB Output is correct
18 Correct 11 ms 25292 KB Output is correct
19 Correct 10 ms 25300 KB Output is correct
20 Correct 10 ms 25300 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25304 KB Output is correct
2 Correct 10 ms 25272 KB Output is correct
3 Correct 10 ms 25300 KB Output is correct
4 Correct 9 ms 25300 KB Output is correct
5 Correct 10 ms 25292 KB Output is correct
6 Correct 10 ms 25324 KB Output is correct
7 Correct 10 ms 25300 KB Output is correct
8 Correct 11 ms 25336 KB Output is correct
9 Correct 10 ms 25300 KB Output is correct
10 Correct 13 ms 25300 KB Output is correct
11 Correct 10 ms 25300 KB Output is correct
12 Correct 10 ms 25300 KB Output is correct
13 Correct 10 ms 25260 KB Output is correct
14 Correct 11 ms 25300 KB Output is correct
15 Correct 11 ms 25300 KB Output is correct
16 Correct 13 ms 25288 KB Output is correct
17 Correct 10 ms 25300 KB Output is correct
18 Correct 10 ms 25268 KB Output is correct
19 Correct 10 ms 25300 KB Output is correct
20 Correct 10 ms 25300 KB Output is correct
21 Correct 12 ms 25252 KB Output is correct
22 Correct 10 ms 25300 KB Output is correct
23 Correct 10 ms 25300 KB Output is correct
24 Correct 10 ms 25300 KB Output is correct
25 Correct 10 ms 25312 KB Output is correct
26 Correct 10 ms 25300 KB Output is correct
27 Correct 10 ms 25332 KB Output is correct
28 Correct 10 ms 25300 KB Output is correct
29 Correct 10 ms 25372 KB Output is correct
30 Correct 12 ms 25380 KB Output is correct
31 Correct 12 ms 25300 KB Output is correct
32 Correct 11 ms 25300 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 65496 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25300 KB Output is correct
2 Correct 10 ms 25300 KB Output is correct
3 Correct 11 ms 25300 KB Output is correct
4 Correct 10 ms 25256 KB Output is correct
5 Correct 10 ms 25300 KB Output is correct
6 Correct 10 ms 25324 KB Output is correct
7 Correct 10 ms 25300 KB Output is correct
8 Correct 10 ms 25300 KB Output is correct
9 Correct 10 ms 25300 KB Output is correct
10 Correct 11 ms 25268 KB Output is correct
11 Correct 11 ms 25300 KB Output is correct
12 Correct 11 ms 25300 KB Output is correct
13 Correct 13 ms 25300 KB Output is correct
14 Correct 11 ms 25300 KB Output is correct
15 Correct 10 ms 25304 KB Output is correct
16 Correct 10 ms 25328 KB Output is correct
17 Correct 10 ms 25300 KB Output is correct
18 Correct 9 ms 25300 KB Output is correct
19 Correct 10 ms 25300 KB Output is correct
20 Correct 10 ms 25300 KB Output is correct
21 Correct 10 ms 25348 KB Output is correct
22 Correct 10 ms 25300 KB Output is correct
23 Correct 11 ms 25392 KB Output is correct
24 Correct 11 ms 25292 KB Output is correct
25 Correct 11 ms 25276 KB Output is correct
26 Correct 10 ms 25320 KB Output is correct
27 Correct 11 ms 25300 KB Output is correct
28 Correct 10 ms 25300 KB Output is correct
29 Correct 10 ms 25300 KB Output is correct
30 Correct 11 ms 25300 KB Output is correct
31 Correct 11 ms 25300 KB Output is correct
32 Correct 10 ms 25300 KB Output is correct
33 Runtime error 65 ms 66628 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25344 KB Output is correct
2 Correct 10 ms 25300 KB Output is correct
3 Correct 10 ms 25300 KB Output is correct
4 Correct 10 ms 25300 KB Output is correct
5 Correct 10 ms 25344 KB Output is correct
6 Correct 10 ms 25300 KB Output is correct
7 Correct 10 ms 25284 KB Output is correct
8 Correct 10 ms 25300 KB Output is correct
9 Correct 10 ms 25300 KB Output is correct
10 Correct 11 ms 25284 KB Output is correct
11 Correct 10 ms 25300 KB Output is correct
12 Correct 10 ms 25300 KB Output is correct
13 Correct 12 ms 25344 KB Output is correct
14 Correct 10 ms 25300 KB Output is correct
15 Correct 10 ms 25280 KB Output is correct
16 Correct 10 ms 25300 KB Output is correct
17 Correct 10 ms 25308 KB Output is correct
18 Correct 10 ms 25300 KB Output is correct
19 Correct 10 ms 25300 KB Output is correct
20 Correct 10 ms 25300 KB Output is correct
21 Correct 10 ms 25260 KB Output is correct
22 Correct 10 ms 25300 KB Output is correct
23 Correct 11 ms 25300 KB Output is correct
24 Correct 11 ms 25316 KB Output is correct
25 Correct 11 ms 25300 KB Output is correct
26 Correct 10 ms 25300 KB Output is correct
27 Correct 10 ms 25300 KB Output is correct
28 Correct 10 ms 25300 KB Output is correct
29 Correct 11 ms 25300 KB Output is correct
30 Correct 11 ms 25380 KB Output is correct
31 Correct 13 ms 25388 KB Output is correct
32 Correct 11 ms 25408 KB Output is correct
33 Runtime error 51 ms 66528 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -