oj.uz

Submission #241656

# Submission time Handle Problem Language Result Execution time Memory
241656 2020-06-25T03:00:59 Z Nightlight Horses (IOI15_horses) C++14
100 / 100
 885 ms 38264 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define L(n) (n << 1)
#define R(n) (n << 1 | 1)
using namespace std;

const long long MOD = 1e9 +7;

int N;
int X[500005], Y[500005];
int treeX[2000000];
long long sumX[2000000];
int mxY[2000000];
int last, now;//product sum suffix skrg
int pointer;//posisi suffix skrg
int residue;//product sum % MOD prefix skrg
//segtree 2 buah dan 1 BIT nice
int kali(long long a, long long b) {
	return a * b > 1000000000 ? 1000000001 : a * b;
}

//segtreeX
void buildX(int n, int l, int r) {
	if(l == r) {
		treeX[n] = X[l];
		sumX[n] = X[l];
//		cout << X[l] << " ";
		return;
	}
	int mid = (l + r) >> 1;
	buildX(L(n), l, mid);
	buildX(R(n), mid + 1, r);
	treeX[n] = kali(treeX[L(n)], treeX[R(n)]);
	sumX[n] = sumX[L(n)] * sumX[R(n)] % MOD;
}

void upX(int n, int l, int r, int pos, int val) {
	if(l == r) {
		treeX[n] = val;
		sumX[n] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upX(L(n), l, mid, pos, val);
	else upX(R(n), mid + 1, r, pos, val);
	treeX[n] = kali(treeX[L(n)], treeX[R(n)]);
	sumX[n] = sumX[L(n)] * sumX[R(n)] % MOD;
}
//query mencari suffix terpanjang yang product sumnya < sum suffix sekarang
void findposX(int n, int l, int r, long long need = last) {
//	cout << l << " " << r << " " << need << "\n";
//	cout << treeX[L(n)] << " " << treeX[R(n)] << "\n";
	if(l == r) {
		pointer = l;
		return;
	}
	int mid = (l + r) >> 1;
	if(treeX[R(n)] >= need) findposX(R(n), mid + 1, r, need);
	else {
		now *= treeX[R(n)];
		need = ceil((double) need / treeX[R(n)]);
		findposX(L(n), l, mid, need);
	}
}

long long sum_query_modX(int n, int l, int r, int ql, int qr) {
	if(ql <= l && r <= qr) {
		return sumX[n];
	}
	int mid = (l + r) >> 1;
	long long res = 1;
	if(ql <= mid) res *= sum_query_modX(L(n), l, mid, ql, qr);
	if(qr > mid) res *= sum_query_modX(R(n), mid + 1, r, ql, qr);
	return res % MOD;
}

int sum_queryX(int n, int l, int r, int ql, int qr) {
	if(ql <= l && r <= qr) {
		return treeX[n];
	}
	int mid = (l + r) >> 1;
	int res = 1;
	if(ql <= mid) res = kali(res, sum_queryX(L(n), l, mid, ql, qr));
	if(qr > mid) res = kali(res, sum_queryX(R(n), mid + 1, r, ql, qr));
	return res;
}

void buildX() {buildX(1, 0, N);}//cout << "\n";}
void upX(int pos, int val) {upX(1, 0, N, pos, val);}
void findposX() {findposX(1, 0, N);}
long long sum_query_modX(int l, int r) {return (l <= r) && (l >= 0) && (r <= N) ? sum_query_modX(1, 0, N, l, r) : 1;}
long long sum_queryX(int l, int r) {return (l <= r) && (l >= 0) && (r <= N) ? sum_queryX(1, 0, N, l, r) : 1;}
//segtree X end
//segtree Y

void buildY(int n, int l, int r) {
	if(l == r) {
		mxY[n] = Y[l];
		return;
	}
	int mid = (l + r) >> 1;
	buildY(L(n), l, mid);
	buildY(R(n), mid + 1, r);
	mxY[n] = max(mxY[L(n)], mxY[R(n)]);
}

void upY(int n, int l, int r, int pos, int val) {
	if(l == r) {
		mxY[n] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upY(L(n), l, mid, pos, val);
	else upY(R(n), mid + 1, r, pos, val);
	mxY[n] = max(mxY[L(n)], mxY[R(n)]);
}

int rmqY(int n, int l, int r, int pos) {
	if(pos <= l) return mxY[n];
	int mid = (l + r) >> 1;
	int res = 0;
	if(pos <= mid) res = rmqY(L(n), l, mid, pos);
	res = max(res, rmqY(R(n), mid + 1, r, pos));
	return res;
}

void buildY() {buildY(1, 1, N);}
void upY(int pos, int val) {upY(1, 1, N, pos, val);}
int rmqY(int pos) {
	if(pos > N || pos < 1) return 0;
	return rmqY(1, 1, N, pos);
}

//segtree Y end

int solve() {
	long long res = 1;	
	long long bef = 1;
	long long sisa = 1;
	last = treeX[1];
//	cout << "\n";
//	buildX();
	if(last != 1000000001) res = rmqY(1);
	else {
		int l = 0, r = N;
		pointer = 0;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(sum_queryX(mid, N) == 1000000001) {
				l = mid + 1;
			}else {
				pointer = mid;
				r = mid - 1;
			}
		}
//		cout << sum_queryX(8, 10) << "\n";
//		cout << sum_queryX(9, 10) << "\n";
		res = rmqY(pointer);
		last = sum_queryX(pointer, N);
		sisa = sum_query_modX(0, pointer - 1);
//		cout << 0 << " " << pointer << ": " << sisa << " <=\n";
//		cout << rmqY(pointer + 1) << "\n";
//		cout << pointer << " - \n";
	}
	while(1) {
		now = 1;
		findposX();
		bef *= last / now;
		res = max(res, bef * rmqY(pointer + 1));
//		cout << bef << " " << rmqY(pointer + 1) << " = " << bef * rmqY(pointer + 1) << "\n";
//		cout << "sum sebelumnya: " << last << "\n";
//		cout << "sum sekarang: " << now << "\n";
//		cout << "posisi skrg: " << pointer << "\n";
//		cout << "bef: " << bef << "\n";
//		cout << "best di array Y di range "<< pointer + 1 << " " << N << " : " << rmqY(pointer + 1) << "\n\n";
		if(now == 1 || pointer >= N) break;
		swap(now, last);
	}
	return (res % MOD * sisa % MOD);
}

int init(int n, int x[], int y[]) {
	N = n;
	for(int i = 0; i < N; i++) X[i] = x[i], Y[i + 1] = y[i];
	X[N] = 1;
	buildX();
	buildY();
	return solve();
}

int updateX(int pos, int val) {	
	X[pos] = val;
	upX(pos, val);
	return solve();
}

int updateY(int pos, int val) {
	upY(pos + 1, val);
	return solve();
}

Compilation message

horses.cpp: In function 'int kali(long long int, long long int)':
horses.cpp:19:28: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return a * b > 1000000000 ? 1000000001 : a * b;
         ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'void findposX(int, int, int, long long int)':
horses.cpp:61:14: warning: conversion to 'long long int' from 'double' may alter its value [-Wfloat-conversion]
   need = ceil((double) need / treeX[R(n)]);
          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int solve()':
horses.cpp:159:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   last = sum_queryX(pointer, N);
          ~~~~~~~~~~^~~~~~~~~~~~
horses.cpp:179:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return (res % MOD * sisa % MOD);
         ~~~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 25640 KB Output is correct
2 Correct 430 ms 38264 KB Output is correct
3 Correct 433 ms 29664 KB Output is correct
4 Correct 468 ms 33336 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 7 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 8 ms 384 KB Output is correct
28 Correct 7 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 6 ms 512 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 7 ms 384 KB Output is correct
33 Correct 83 ms 28664 KB Output is correct
34 Correct 81 ms 28664 KB Output is correct
35 Correct 110 ms 35704 KB Output is correct
36 Correct 112 ms 35580 KB Output is correct
37 Correct 125 ms 26912 KB Output is correct
38 Correct 79 ms 27640 KB Output is correct
39 Correct 40 ms 26624 KB Output is correct
40 Correct 88 ms 30584 KB Output is correct
41 Correct 66 ms 26744 KB Output is correct
42 Correct 107 ms 26872 KB Output is correct
43 Correct 56 ms 30968 KB Output is correct
44 Correct 55 ms 30968 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 9 ms 384 KB Output is correct
28 Correct 7 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 6 ms 384 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 8 ms 384 KB Output is correct
33 Correct 751 ms 29560 KB Output is correct
34 Correct 424 ms 38264 KB Output is correct
35 Correct 430 ms 29608 KB Output is correct
36 Correct 476 ms 33272 KB Output is correct
37 Correct 93 ms 28664 KB Output is correct
38 Correct 84 ms 28664 KB Output is correct
39 Correct 120 ms 35576 KB Output is correct
40 Correct 106 ms 35704 KB Output is correct
41 Correct 140 ms 26752 KB Output is correct
42 Correct 86 ms 27644 KB Output is correct
43 Correct 43 ms 26616 KB Output is correct
44 Correct 86 ms 30584 KB Output is correct
45 Correct 69 ms 26744 KB Output is correct
46 Correct 103 ms 26744 KB Output is correct
47 Correct 58 ms 30968 KB Output is correct
48 Correct 55 ms 31096 KB Output is correct
49 Correct 426 ms 30844 KB Output is correct
50 Correct 396 ms 30584 KB Output is correct
51 Correct 450 ms 37516 KB Output is correct
52 Correct 385 ms 36984 KB Output is correct
53 Correct 885 ms 29164 KB Output is correct
54 Correct 469 ms 29560 KB Output is correct
55 Correct 124 ms 27768 KB Output is correct
56 Correct 418 ms 32376 KB Output is correct
57 Correct 360 ms 28648 KB Output is correct
58 Correct 695 ms 29080 KB Output is correct
59 Correct 53 ms 30968 KB Output is correct