oj.uz

Submission #64669

# Submission time Handle Problem Language Result Execution time Memory
64669 2018-08-05T11:09:03 Z FLDutchman Horses (IOI15_horses) C++14
100 / 100
 963 ms 177712 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
#define fst first
#define snd second
#define LSB(k) k&-k

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int mod = 1e9+7;

struct segtree{
	vi t;
	segtree(int N){
		t.assign(4*N, 0);
	}	

	segtree(){}

	void update(int n){
		t[n] = max(t[n<<1], t[n<<1|1]);
	}

	void modify(int i, int v, int lb, int rb, int n = 1){
		if(lb + 1 == rb) {
			t[n] = v;
			return;
		}
		int mb = (lb+rb)/2;
		if(i < mb) modify(i, v, lb, mb, n<<1);
		else modify(i, v, mb, rb, n<<1|1);
		update(n);
	}

	int rmq(int l, int r, int lb, int rb, int n = 1){
		//cout << "rmq " << l << " " << r << " " << lb << " " << rb << " " << n << endl;
		if(l <= lb and rb <= r) return t[n];
		int mb = (lb + rb)/2;
		int res = 0;
		if(l < mb) res = max(res, rmq(l, r, lb, mb, n<<1));
		if (r > mb) res = max(res, rmq(l, r, mb, rb, n<<1|1));
		return res;
	}
};

int mpow(int a, int b){
	if(b == 0) return 1;
	if(b == 1) return a;
	if(b & 1) return a * mpow(a*a%mod, b>>1) % mod;
	return mpow(a*a%mod, b>>1);
}

int N;
vi X, Xinv, Y;
segtree tree;
multiset<int> nonunit;
int prod;

int getBest(){
	//cout << prod << endl;
	int i = N-1;
	int y = Y[i];
	int p = prod;
	while(y < mod && i > 0){
		//cout << p << " " << y << endl;
		if(X[i] == 1) { // Something is wrong here
			// precompute it and rmq?
			auto it = prev(nonunit.upper_bound(i));
			//cout << *it << " " << i << endl;
			y = max(y,  tree.rmq(max(*it, 0LL), i, 0, N));
			//cout << tree.rmq(max(*it, 0LL), i, 0, N) << endl;
			i = *it;
		} else {
			p = p * Xinv[i] % mod;
			y = max(y * X[i], Y[i-1]);
			i--;
		}
	}
	y %= mod;
	//cout << p << " " << y << endl;
	return p * y % mod;
}

INT init(INT n, INT x[], INT y[]) {
	N = n;
	tree = segtree(N);
	prod = 1;
	nonunit.insert(-1);
	FOR(i, 0, N) Y.pb(y[i]), X.pb(x[i]), tree.modify(i, y[i], 0, N), Xinv.pb(mpow(x[i], mod-2)), prod = prod * X[i] % mod;
	FOR(i, 0, N) if(X[i] != 1) nonunit.insert(i);
	return getBest();
}

//void rem(int i){
//	nonunit.erase(i);
//
//}

INT updateX(INT pos, INT val) {	
	if(X[pos] != 1) nonunit.erase(pos);
	prod = prod * Xinv[pos] % mod * val % mod;
	X[pos] = val;
	Xinv[pos] = mpow(val, mod-2);
	if(val != 1) nonunit.insert(pos);



	return getBest();
}

INT updateY(INT pos, INT val) {
	Y[pos] = val;
	tree.modify(pos, val, 0, N);
	return getBest();
}


/*
12
1 1 1 1 1 6 1 1 1 1 1 10
30 20 3 5 10 3 2 5 7 3 4 1
2
2 0 1
1 4 5

*/

Compilation message

horses.cpp: In function 'INT init(INT, INT*, INT*)':
horses.cpp:99:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~
horses.cpp: In function 'INT updateX(INT, INT)':
horses.cpp:116:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~
horses.cpp: In function 'INT updateY(INT, INT)':
horses.cpp:122:16: warning: conversion to 'INT {aka int}' from 'long long int' may alter its value [-Wconversion]
  return getBest();
         ~~~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 56712 KB Output is correct
2 Correct 626 ms 56712 KB Output is correct
3 Correct 562 ms 56808 KB Output is correct
4 Correct 615 ms 56808 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 56808 KB Output is correct
2 Correct 2 ms 56808 KB Output is correct
3 Correct 4 ms 56808 KB Output is correct
4 Correct 2 ms 56808 KB Output is correct
5 Correct 3 ms 56808 KB Output is correct
6 Correct 3 ms 56808 KB Output is correct
7 Correct 2 ms 56808 KB Output is correct
8 Correct 2 ms 56808 KB Output is correct
9 Correct 2 ms 56808 KB Output is correct
10 Correct 2 ms 56808 KB Output is correct
11 Correct 2 ms 56808 KB Output is correct
12 Correct 2 ms 56808 KB Output is correct
13 Correct 2 ms 56808 KB Output is correct
14 Correct 2 ms 56808 KB Output is correct
15 Correct 2 ms 56808 KB Output is correct
16 Correct 2 ms 56808 KB Output is correct
17 Correct 2 ms 56808 KB Output is correct
18 Correct 2 ms 56808 KB Output is correct
19 Correct 2 ms 56808 KB Output is correct
20 Correct 4 ms 56808 KB Output is correct
21 Correct 2 ms 56808 KB Output is correct
22 Correct 3 ms 56808 KB Output is correct
23 Correct 4 ms 56808 KB Output is correct
24 Correct 5 ms 56808 KB Output is correct
25 Correct 3 ms 56808 KB Output is correct
26 Correct 10 ms 56808 KB Output is correct
27 Correct 7 ms 56808 KB Output is correct
28 Correct 3 ms 56808 KB Output is correct
29 Correct 4 ms 56808 KB Output is correct
30 Correct 4 ms 56808 KB Output is correct
31 Correct 3 ms 56808 KB Output is correct
32 Correct 18 ms 56808 KB Output is correct
33 Correct 269 ms 56808 KB Output is correct
34 Correct 284 ms 56808 KB Output is correct
35 Correct 462 ms 58956 KB Output is correct
36 Correct 407 ms 58956 KB Output is correct
37 Correct 271 ms 58956 KB Output is correct
38 Correct 374 ms 58956 KB Output is correct
39 Correct 242 ms 58956 KB Output is correct
40 Correct 456 ms 70164 KB Output is correct
41 Correct 237 ms 70164 KB Output is correct
42 Correct 327 ms 70164 KB Output is correct
43 Correct 437 ms 80572 KB Output is correct
44 Correct 452 ms 86880 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 86880 KB Output is correct
2 Correct 2 ms 86880 KB Output is correct
3 Correct 3 ms 86880 KB Output is correct
4 Correct 2 ms 86880 KB Output is correct
5 Correct 3 ms 86880 KB Output is correct
6 Correct 3 ms 86880 KB Output is correct
7 Correct 2 ms 86880 KB Output is correct
8 Correct 4 ms 86880 KB Output is correct
9 Correct 4 ms 86880 KB Output is correct
10 Correct 2 ms 86880 KB Output is correct
11 Correct 3 ms 86880 KB Output is correct
12 Correct 2 ms 86880 KB Output is correct
13 Correct 2 ms 86880 KB Output is correct
14 Correct 3 ms 86880 KB Output is correct
15 Correct 3 ms 86880 KB Output is correct
16 Correct 2 ms 86880 KB Output is correct
17 Correct 2 ms 86880 KB Output is correct
18 Correct 2 ms 86880 KB Output is correct
19 Correct 2 ms 86880 KB Output is correct
20 Correct 2 ms 86880 KB Output is correct
21 Correct 3 ms 86880 KB Output is correct
22 Correct 2 ms 86880 KB Output is correct
23 Correct 3 ms 86880 KB Output is correct
24 Correct 4 ms 86880 KB Output is correct
25 Correct 4 ms 86880 KB Output is correct
26 Correct 3 ms 86880 KB Output is correct
27 Correct 7 ms 86880 KB Output is correct
28 Correct 4 ms 86880 KB Output is correct
29 Correct 3 ms 86880 KB Output is correct
30 Correct 3 ms 86880 KB Output is correct
31 Correct 3 ms 86880 KB Output is correct
32 Correct 5 ms 86880 KB Output is correct
33 Correct 432 ms 87772 KB Output is correct
34 Correct 653 ms 87996 KB Output is correct
35 Correct 567 ms 87996 KB Output is correct
36 Correct 677 ms 87996 KB Output is correct
37 Correct 221 ms 87996 KB Output is correct
38 Correct 255 ms 87996 KB Output is correct
39 Correct 498 ms 87996 KB Output is correct
40 Correct 449 ms 87996 KB Output is correct
41 Correct 292 ms 87996 KB Output is correct
42 Correct 306 ms 87996 KB Output is correct
43 Correct 215 ms 87996 KB Output is correct
44 Correct 408 ms 97988 KB Output is correct
45 Correct 205 ms 97988 KB Output is correct
46 Correct 275 ms 97988 KB Output is correct
47 Correct 393 ms 108320 KB Output is correct
48 Correct 480 ms 114836 KB Output is correct
49 Correct 371 ms 114836 KB Output is correct
50 Correct 301 ms 114836 KB Output is correct
51 Correct 646 ms 137684 KB Output is correct
52 Correct 531 ms 149080 KB Output is correct
53 Correct 963 ms 149080 KB Output is correct
54 Correct 512 ms 149080 KB Output is correct
55 Correct 317 ms 149080 KB Output is correct
56 Correct 568 ms 166356 KB Output is correct
57 Correct 303 ms 166356 KB Output is correct
58 Correct 715 ms 166356 KB Output is correct
59 Correct 456 ms 177712 KB Output is correct