oj.uz

Submission #115614

# Submission time Handle Problem Language Result Execution time Memory
115614 2019-06-08T10:24:24 Z E869120 Horses (IOI15_horses) C++14
100 / 100
 843 ms 64700 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

const long long mod = 1000000007;

class RangeMax {
	public:
	vector<long long> dat; int size_ = 1;
	
	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, 0);
	}
	void update(int pos, int x) {
		pos += size_; dat[pos] = x;
		while (pos >= 2) {
			pos >>= 1;
			dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
		}
	}
	long long query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u];
		if (r <= a || b <= l) return 0LL;
		long long s1 = query_(l, r, a, (a + b) >> 1, u * 2);
		long long s2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return max(s1, s2);
	}
	long long query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 30; i++) {
		if ((b & (1LL << i)) != 0) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long INV(long long x) {
	return modpow(x, mod - 2, mod);
}

set<pair<int, long long>>S; RangeMax Z;
long long NN, A[500009], B[500009], TotalSum = 1;

long long calculate() {
	auto itr = S.end(); long long L = 1; vector<pair<long long, long long>> vec;
	while (itr != S.begin()) {
		itr--;
		pair<int, long long> E = (*itr);
		long long D = Z.query(1LL * E.first, NN + 1);
		//cout << "[" << E.first << ", " << NN + 1 << "] = " << D << endl;
		vec.push_back(make_pair(D, L));
		
		L *= E.second; if (L > (1LL << 30)) break;
	}
	if (L <= (1LL << 30)) vec.push_back(make_pair(Z.query(0, NN + 1), L));
	
	/*cout << "vec : " << endl;
	for (int i = 0; i < vec.size(); i++) cout << vec[i].first << " / " << vec[i].second << endl;
	cout << endl;*/
	
	long long maxn = 0;
	for (int i = 0; i < (int)vec.size(); i++) {
		maxn = max(maxn, 1LL * vec[i].first * (vec[vec.size() - 1].second / vec[i].second));
	}
	maxn %= mod;
	
	long long s1 = TotalSum;
	if ((int)vec.size() >= 1) { s1 *= INV(vec[vec.size() - 1].second); s1 %= mod; }
	
	return maxn * s1 % mod;
}

int init(int N, int X[], int Y[]) {
	NN = N; Z.init(NN + 2);
	for (int i = 0; i < N; i++) { A[i] = X[i]; B[i] = Y[i]; }
	for (int i = 0; i < N; i++) {
		Z.update(i, B[i]); TotalSum *= (1LL * A[i]); TotalSum %= mod;
		if (A[i] != 1) S.insert(make_pair(i, A[i]));
	}
	return calculate();
}

int updateX(int i, int val) {
	TotalSum *= INV(A[i]); TotalSum %= mod; if (A[i] != 1) S.erase(make_pair(i, A[i]));
	A[i] = val;
	TotalSum *= A[i]; TotalSum %= mod; if (A[i] != 1) S.insert(make_pair(i, A[i]));
	return calculate();
}

int updateY(int pos, int val) {
	Z.update(pos, val);
	return calculate();
}

Compilation message

horses.cpp: In function 'long long int calculate()':
horses.cpp:55:43: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   long long D = Z.query(1LL * E.first, NN + 1);
                                        ~~~^~~
horses.cpp:61:62: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  if (L <= (1LL << 30)) vec.push_back(make_pair(Z.query(0, NN + 1), L));
                                                           ~~~^~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:80:20: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  NN = N; Z.init(NN + 2);
                 ~~~^~~
horses.cpp:83:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
   Z.update(i, B[i]); TotalSum *= (1LL * A[i]); TotalSum %= mod;
               ~~~^
horses.cpp:86:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return calculate();
         ~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:93:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return calculate();
         ~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:98:18: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return calculate();
         ~~~~~~~~~^~

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 384 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 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 380 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 256 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 256 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 256 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 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 356 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 384 KB Output is correct
25 Correct 4 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 3 ms 512 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 52784 KB Output is correct
2 Correct 469 ms 52848 KB Output is correct
3 Correct 460 ms 52728 KB Output is correct
4 Correct 573 ms 52748 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 256 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 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 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 384 KB Output is correct
25 Correct 4 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 3 ms 412 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 66 ms 20856 KB Output is correct
34 Correct 61 ms 24568 KB Output is correct
35 Correct 277 ms 62684 KB Output is correct
36 Correct 256 ms 62456 KB Output is correct
37 Correct 122 ms 22776 KB Output is correct
38 Correct 152 ms 39416 KB Output is correct
39 Correct 55 ms 22520 KB Output is correct
40 Correct 242 ms 57720 KB Output is correct
41 Correct 83 ms 22520 KB Output is correct
42 Correct 103 ms 22520 KB Output is correct
43 Correct 237 ms 57976 KB Output is correct
44 Correct 244 ms 57976 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 300 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 256 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 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 316 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 256 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 4 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 4 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 4 ms 512 KB Output is correct
29 Correct 3 ms 380 KB Output is correct
30 Correct 3 ms 512 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 6 ms 384 KB Output is correct
33 Correct 843 ms 52884 KB Output is correct
34 Correct 481 ms 52856 KB Output is correct
35 Correct 479 ms 52972 KB Output is correct
36 Correct 603 ms 52984 KB Output is correct
37 Correct 67 ms 20728 KB Output is correct
38 Correct 65 ms 24440 KB Output is correct
39 Correct 290 ms 62632 KB Output is correct
40 Correct 269 ms 62684 KB Output is correct
41 Correct 120 ms 22648 KB Output is correct
42 Correct 154 ms 39308 KB Output is correct
43 Correct 76 ms 22496 KB Output is correct
44 Correct 255 ms 57624 KB Output is correct
45 Correct 84 ms 22392 KB Output is correct
46 Correct 102 ms 22460 KB Output is correct
47 Correct 261 ms 58056 KB Output is correct
48 Correct 269 ms 58104 KB Output is correct
49 Correct 187 ms 27896 KB Output is correct
50 Correct 172 ms 27916 KB Output is correct
51 Correct 505 ms 64700 KB Output is correct
52 Correct 399 ms 64120 KB Output is correct
53 Correct 824 ms 26216 KB Output is correct
54 Correct 345 ms 44024 KB Output is correct
55 Correct 166 ms 23416 KB Output is correct
56 Correct 408 ms 59384 KB Output is correct
57 Correct 467 ms 24144 KB Output is correct
58 Correct 636 ms 24624 KB Output is correct
59 Correct 274 ms 58180 KB Output is correct