oj.uz

Submission #118935

# Submission time Handle Problem Language Result Execution time Memory
118935 2019-06-20T05:26:29 Z TuGSGeReL Horses (IOI15_horses) C++14
100 / 100
 538 ms 52212 KB 
#include "horses.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;

int mod = 1e9 + 7, ans[1500001], n, terx[1500001], tery[1500001], sx[1500001];
double mx[1500001], sgx[1500001], sgy[1500001];

void upd(int node, int idx, int l, int r, int x, int y)
{
	if ( l > idx || r < idx )
		return;
	
	if ( l == r ) {
		if ( x != -1 ) {
			sgx[node] = log10(x);
			terx[node] = x;
		}
		
		if ( y != -1 ) {
			sgy[node] = log10(y);
			tery[node] = y;
		}
		
		sx[node] = terx[node];
		mx[node] = sgx[node] + sgy[node];
		ans[node] = (1ll * terx[node] * tery[node]) % mod;
		return;
	}
	
	int mid = (l + r) / 2;
	
	upd(node * 2, idx, l, mid, x, y);
	upd(node * 2 + 1, idx, mid + 1, r, x, y);
	
	sgx[node] = sgx[node * 2] + sgx[node * 2 + 1];
	sx[node] = (1ll * sx[node * 2] * sx[node * 2 + 1]) % mod;
	
	if ( mx[node * 2] > mx[node * 2 + 1] + sgx[node * 2] ) {
		mx[node] = mx[node * 2];
		ans[node] = ans[node * 2];
	} else {
		mx[node] = mx[node * 2 + 1] + sgx[node * 2];
		ans[node] = (1ll * ans[node * 2 + 1] * sx[node * 2]) % mod;
	}
}

int init(int N, int X[], int Y[]) {
	n = N;
		
	for (ll i = 0; i < N; i++)
		upd(1, i, 0, N - 1, X[i], Y[i]);
		
	return ans[1];
}

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

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

Compilation message

horses.cpp: In function 'void upd(int, int, int, int, int, int)':
horses.cpp:46:47: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   ans[node] = (1ll * terx[node] * tery[node]) % mod;
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:56:53: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  sx[node] = (1ll * sx[node * 2] * sx[node * 2 + 1]) % mod;
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:63:56: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   ans[node] = (1ll * ans[node * 2 + 1] * sx[node * 2]) % mod;
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:71:33: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   upd(1, i, 0, N - 1, X[i], Y[i]);
                                 ^

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 3 ms 512 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 3 ms 512 KB Output is correct
31 Correct 3 ms 512 KB Output is correct
32 Correct 3 ms 512 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 43892 KB Output is correct
2 Correct 498 ms 52156 KB Output is correct
3 Correct 467 ms 45944 KB Output is correct
4 Correct 466 ms 50040 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 3 ms 512 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 3 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 306 ms 41380 KB Output is correct
34 Correct 306 ms 45420 KB Output is correct
35 Correct 342 ms 51432 KB Output is correct
36 Correct 344 ms 51320 KB Output is correct
37 Correct 333 ms 43632 KB Output is correct
38 Correct 314 ms 44280 KB Output is correct
39 Correct 323 ms 43440 KB Output is correct
40 Correct 352 ms 47292 KB Output is correct
41 Correct 324 ms 43396 KB Output is correct
42 Correct 316 ms 43512 KB Output is correct
43 Correct 337 ms 47568 KB Output is correct
44 Correct 340 ms 47604 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 3 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 512 KB Output is correct
29 Correct 3 ms 512 KB Output is correct
30 Correct 3 ms 512 KB Output is correct
31 Correct 2 ms 512 KB Output is correct
32 Correct 3 ms 512 KB Output is correct
33 Correct 386 ms 43896 KB Output is correct
34 Correct 538 ms 52212 KB Output is correct
35 Correct 483 ms 46072 KB Output is correct
36 Correct 476 ms 49908 KB Output is correct
37 Correct 315 ms 45304 KB Output is correct
38 Correct 316 ms 45260 KB Output is correct
39 Correct 346 ms 51508 KB Output is correct
40 Correct 353 ms 51396 KB Output is correct
41 Correct 338 ms 43384 KB Output is correct
42 Correct 308 ms 44280 KB Output is correct
43 Correct 325 ms 43284 KB Output is correct
44 Correct 352 ms 47208 KB Output is correct
45 Correct 337 ms 43512 KB Output is correct
46 Correct 316 ms 43492 KB Output is correct
47 Correct 338 ms 47608 KB Output is correct
48 Correct 343 ms 47844 KB Output is correct
49 Correct 437 ms 47352 KB Output is correct
50 Correct 441 ms 47360 KB Output is correct
51 Correct 402 ms 52104 KB Output is correct
52 Correct 402 ms 52032 KB Output is correct
53 Correct 467 ms 45640 KB Output is correct
54 Correct 380 ms 46140 KB Output is correct
55 Correct 385 ms 44536 KB Output is correct
56 Correct 415 ms 49144 KB Output is correct
57 Correct 379 ms 45180 KB Output is correct
58 Correct 426 ms 45560 KB Output is correct
59 Correct 346 ms 47688 KB Output is correct