oj.uz

Submission #121039

# Submission time Handle Problem Language Result Execution time Memory
121039 2019-06-26T03:47:22 Z khulegub Horses (IOI15_horses) C++14
100 / 100
 864 ms 60824 KB 
#include "horses.h"
#include<bits/stdc++.h>
#define ll(x) x*2+1
#define rr(x) x*2+2
#define eps 1e-9
using namespace std;
typedef long long i64;
int mod = 1e9 + 7;
 
// vector<i64> st;
 
vector<double> st_inv;
vector<int> st_max;
vector<i64> st_mult;
vector<int> x, y;
int n;
void build_mult(int l, int r, int node){
	if(l == r){
		st_mult[node] = x[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build_mult(l, mid, ll(node));
	build_mult(mid + 1, r, rr(node));
	st_mult[node] = (st_mult[ll(node)] * st_mult[rr(node)]) % mod;
}
void update_mult(int pos, int l, int r, int node){
	if(l == r){
		st_mult[node] = x[l];
		return ;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) update_mult(pos, l, mid, ll(node));
	else update_mult(pos, mid + 1, r, rr(node));
	st_mult[node] = (st_mult[ll(node)] * st_mult[rr(node)]) % mod;
}
i64 query_mult(int ql, int qr, int l, int r, int node){
	if(qr < l || r < ql) return 1;
	if(ql <= l && r <= qr) return st_mult[node];
	int mid = (l + r) >> 1;
	return (query_mult(ql, qr, l, mid, ll(node)) * query_mult(ql, qr, mid + 1, r, rr(node))) % mod;
}	
void build_inv(int l, int r, int node){
	if(l == r){
		st_inv[node] = 1.0 / ((double) x[l]);
		return ;
	}
	int mid = (l + r) >> 1;
	build_inv(l, mid, ll(node));
	build_inv(mid + 1, r, rr(node));
	st_inv[node] = st_inv[ll(node)] * st_inv[rr(node)];
}
void update_inv(int pos, int l, int r, int node){
	if(l == r){
		st_inv[node] = 1.0 / ((double) x[l]);
		return ;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) update_inv(pos, l, mid, ll(node));
	else update_inv(pos, mid + 1, r, rr(node));
	st_inv[node] = st_inv[ll(node)] * st_inv[rr(node)];
}
double query_inv(int ql, int qr, int l, int r, int node){
	if(qr < l || r < ql) return 1.0;
	if(ql <= l && r <= qr) return st_inv[node];
	int mid = (l + r) >> 1;
	return query_inv(ql, qr, l, mid, ll(node)) * query_inv(ql, qr, mid + 1, r, rr(node));
}
double query_inv(int ql, int qr){
	return query_inv(ql, qr, 0, n - 1, 0);
}
void build_max(int l, int r, int node){
	if(l == r){
		st_max[node] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	build_max(l, mid, ll(node));
	build_max(mid + 1, r, rr(node));
	int li = st_max[ll(node)], ri = st_max[rr(node)];
	double inv = query_inv(li + 1, ri);
	double haritsa = ((double) y[ri]) / ((double) y[li]);
	if(haritsa > inv) st_max[node] = ri;
	else st_max[node] = li;
}
void update_max(int pos, int l, int r, int node){
	if(r < pos || pos < l) return ;
	if(l == r){
		st_max[node] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	update_max(pos, l, mid, ll(node));
	update_max(pos, mid + 1, r, rr(node));
	int li = st_max[ll(node)], ri = st_max[rr(node)];
	double inv = query_inv(li + 1, ri);
	double haritsa = ((double) y[ri]) / ((double) y[li]);
	if(haritsa >= inv) st_max[node] = ri;
	else st_max[node] = li;
}
int query_max(int ql, int qr, int l, int r, int node){
	if(qr < l || r < ql) return -1;
	if(ql <= l && r <= qr) return st_max[node];
	int mid = (l + r) >> 1;
	int li = query_max(ql, qr, l, mid, ll(node));
	int ri = query_max(ql, qr, mid + 1, r, rr(node));
	if(li == -1){
		return ri;
	}
	else if(ri == -1){
		return li;
	}
	else{
		double inv = query_inv(li + 1, ri);
		double haritsa = ((double) y[ri]) / ((double) y[li]);
		if(haritsa > inv) return ri;
		else return li;
	}
}
int query_max(int ql, int qr){
	return query_max(ql, qr, 0, n-1, 0);
}
// void update()
 
int init(int N, int X[], int Y[]){
	n = N;
	x.resize(n);
	y.resize(n);
	st_inv.resize(4*n);
	st_max.resize(4*n);
	st_mult.resize(4*n);
	for(int i = 0; i < n; i++){
		x[i] = X[i];
		y[i] = Y[i];
	}
	build_inv(0, n-1, 0);
	build_max(0, n-1, 0);
	build_mult(0, n-1, 0);
	// cout << query_max(0, n-1);
	int indx = query_max(0, n-1);
	return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
}
int updateX(int pos, int val){
	x[pos] = val;
	update_inv(pos, 0, n-1, 0);
	// build_max(0, n-1, 0);
	update_max(pos, 0, n-1, 0);
	update_mult(pos, 0, n-1, 0);
	int indx = query_max(0, n-1);
	return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
}
int updateY(int pos, int val){
	y[pos] = val;
	// build_max(0, n-1, 0);
	update_max(pos, 0, n-1, 0);
	int indx = query_max(0, n-1);
	return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:141:52: warning: conversion to 'int' from 'i64 {aka long long int}' may alter its value [-Wconversion]
  return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:150:52: warning: conversion to 'int' from 'i64 {aka long long int}' may alter its value [-Wconversion]
  return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:157:52: warning: conversion to 'int' from 'i64 {aka long long int}' may alter its value [-Wconversion]
  return (query_mult(0, indx, 0, n-1, 0) * y[indx]) % mod;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 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 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 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 256 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 256 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 256 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 1 ms 384 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 4 ms 384 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 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 4 ms 384 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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 48432 KB Output is correct
2 Correct 553 ms 53704 KB Output is correct
3 Correct 642 ms 52080 KB Output is correct
4 Correct 666 ms 55940 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 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 256 KB Output is correct
14 Correct 3 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 356 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 356 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 356 KB Output is correct
22 Correct 2 ms 300 KB Output is correct
23 Correct 3 ms 412 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 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 3 ms 384 KB Output is correct
29 Correct 3 ms 384 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 218 ms 51436 KB Output is correct
34 Correct 211 ms 51472 KB Output is correct
35 Correct 178 ms 58204 KB Output is correct
36 Correct 170 ms 58228 KB Output is correct
37 Correct 214 ms 49456 KB Output is correct
38 Correct 178 ms 50368 KB Output is correct
39 Correct 184 ms 49408 KB Output is correct
40 Correct 158 ms 53244 KB Output is correct
41 Correct 177 ms 49396 KB Output is correct
42 Correct 172 ms 49424 KB Output is correct
43 Correct 137 ms 53712 KB Output is correct
44 Correct 138 ms 53720 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 412 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 304 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 436 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 4 ms 384 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 460 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 4 ms 384 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 387 ms 52124 KB Output is correct
34 Correct 541 ms 60824 KB Output is correct
35 Correct 623 ms 52092 KB Output is correct
36 Correct 675 ms 55984 KB Output is correct
37 Correct 228 ms 51340 KB Output is correct
38 Correct 220 ms 51364 KB Output is correct
39 Correct 185 ms 58236 KB Output is correct
40 Correct 175 ms 58248 KB Output is correct
41 Correct 218 ms 49576 KB Output is correct
42 Correct 173 ms 50524 KB Output is correct
43 Correct 186 ms 49400 KB Output is correct
44 Correct 162 ms 53244 KB Output is correct
45 Correct 175 ms 49400 KB Output is correct
46 Correct 187 ms 49532 KB Output is correct
47 Correct 143 ms 53720 KB Output is correct
48 Correct 143 ms 53712 KB Output is correct
49 Correct 856 ms 53268 KB Output is correct
50 Correct 772 ms 53312 KB Output is correct
51 Correct 441 ms 60148 KB Output is correct
52 Correct 323 ms 59632 KB Output is correct
53 Correct 864 ms 51668 KB Output is correct
54 Correct 430 ms 52204 KB Output is correct
55 Correct 599 ms 50600 KB Output is correct
56 Correct 332 ms 55212 KB Output is correct
57 Correct 494 ms 51012 KB Output is correct
58 Correct 540 ms 51560 KB Output is correct
59 Correct 136 ms 53708 KB Output is correct