oj.uz

답안 #342811

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342811 2021-01-02T21:42:45 Z monus1042 말 (IOI15_horses) C++17
100 / 100
 720 ms 131504 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
typedef pair<int,int> ii;
typedef long double ld;

const ll MOD = 1000000007;
const int MAXS = 5e5+10;
int n;
vector<ll> x, y;
vector<ld> accbasis;
vector<pair<ld, int>> seg(MAXS * 4);
vector<ld> lazy(MAXS *4);
vector<ll> fen(MAXS, 1LL); // using 1 indexing in this

ll power(ll b, ll exp){
	if (exp == 0) return 1LL;
	if (exp&1) return (power((b*b) % MOD, exp/2) * b) % MOD;
	return power((b*b)%MOD, exp/2) % MOD;
}

void build(int node, int l, int r){
	if (l == r){
		seg[node] = make_pair(accbasis[l], l);
		return;
	}
	int mid = (l + r) / 2;
	build(node *2, l, mid);
	build(node*2 +1, mid+1, r);
	if (seg[node*2].first > seg[node*2+1].first) seg[node] = seg[node*2];
	else seg[node] = seg[node*2+1];
}

void update(int node, int l, int r, int xl, int xr, ld delta){
	if (lazy[node] != 0.0){
		seg[node].first += lazy[node];
		if (l!=r){
			lazy[node*2] += lazy[node];
			lazy[node*2+1] += lazy[node];
		}
		lazy[node] = 0.0;
	}
	if (l > xr || r < xl) return;
	if (xl <= l && r <= xr){
		seg[node].first += delta;
		if (l != r){
			lazy[node*2] += delta;
			lazy[node*2+1] += delta;
		}
		return;
	}
	int mid = (l+r)/2;
	update(node*2, l, mid, xl, xr, delta);
	update(node*2+1, mid+1, r, xl, xr, delta);
	if (seg[node*2].first > seg[node*2+1].first) seg[node] = seg[node*2];
	else seg[node] = seg[node*2+1];
}

void upd(int pos, ll factor){
	while(pos <= n){
		fen[pos] = (fen[pos] * factor) % MOD;
		pos += pos&-pos;
	}
}

ll que(int pos){
	ll answer = 1LL;
	while(pos){
		answer = (answer * fen[pos]) % MOD;
		pos -= pos&-pos;
	}
	return answer;
}

int solve(){
	int position = seg[1].second + 1;
	ll answer = (que(position) * y[position-1]) % MOD;
	return (int)answer;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i=0; i<n; i++) x.push_back(X[i]), y.push_back(Y[i]);
	ld acc = 0.0;
	for (int i=0; i<n; i++){
		acc = acc + (ld)log10(x[i]);
		accbasis.push_back(acc);
		upd(i+1, x[i]);
	}
	build(1, 0, n-1);
	for (int i=0; i<n; i++){
		update(1, 0, n-1, i, i, (ld)log10(y[i]));
	}
	return solve();
}

int updateX(int pos, int val) {
	ll inv = power(x[pos], MOD-2);
	upd(pos+1, inv);
	upd(pos+1, (ll)val);
	ld delta = (ld)log10(val) - (ld)log10(x[pos]);
	update(1, 0, n-1, pos, n-1, delta);
	x[pos] = val;
	return solve();
}

int updateY(int pos, int val) {
	ld delta = (ld)log10(val) - log10(y[pos]);
	update(1, 0, n-1, pos, pos, delta);
	y[pos] = val;
	return solve();
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 98156 KB Output is correct
2 Correct 53 ms 98156 KB Output is correct
3 Correct 63 ms 98156 KB Output is correct
4 Correct 54 ms 98156 KB Output is correct
5 Correct 53 ms 98156 KB Output is correct
6 Correct 54 ms 98156 KB Output is correct
7 Correct 55 ms 98156 KB Output is correct
8 Correct 54 ms 98156 KB Output is correct
9 Correct 54 ms 98156 KB Output is correct
10 Correct 55 ms 98156 KB Output is correct
11 Correct 64 ms 98156 KB Output is correct
12 Correct 54 ms 98156 KB Output is correct
13 Correct 54 ms 98156 KB Output is correct
14 Correct 56 ms 98196 KB Output is correct
15 Correct 57 ms 98188 KB Output is correct
16 Correct 54 ms 98156 KB Output is correct
17 Correct 61 ms 98284 KB Output is correct
18 Correct 54 ms 98156 KB Output is correct
19 Correct 54 ms 98156 KB Output is correct
20 Correct 54 ms 98176 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 98284 KB Output is correct
2 Correct 54 ms 98176 KB Output is correct
3 Correct 54 ms 98156 KB Output is correct
4 Correct 57 ms 98284 KB Output is correct
5 Correct 54 ms 98200 KB Output is correct
6 Correct 53 ms 98156 KB Output is correct
7 Correct 53 ms 98156 KB Output is correct
8 Correct 53 ms 98156 KB Output is correct
9 Correct 54 ms 98284 KB Output is correct
10 Correct 55 ms 98156 KB Output is correct
11 Correct 54 ms 98156 KB Output is correct
12 Correct 54 ms 98156 KB Output is correct
13 Correct 55 ms 98156 KB Output is correct
14 Correct 53 ms 98284 KB Output is correct
15 Correct 53 ms 98156 KB Output is correct
16 Correct 54 ms 98156 KB Output is correct
17 Correct 63 ms 98156 KB Output is correct
18 Correct 59 ms 98156 KB Output is correct
19 Correct 59 ms 98156 KB Output is correct
20 Correct 57 ms 98156 KB Output is correct
21 Correct 54 ms 98284 KB Output is correct
22 Correct 55 ms 98156 KB Output is correct
23 Correct 55 ms 98284 KB Output is correct
24 Correct 56 ms 98284 KB Output is correct
25 Correct 55 ms 98284 KB Output is correct
26 Correct 56 ms 98284 KB Output is correct
27 Correct 55 ms 98284 KB Output is correct
28 Correct 56 ms 98284 KB Output is correct
29 Correct 62 ms 98224 KB Output is correct
30 Correct 55 ms 98284 KB Output is correct
31 Correct 54 ms 98412 KB Output is correct
32 Correct 55 ms 98284 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 455 ms 119780 KB Output is correct
2 Correct 720 ms 125532 KB Output is correct
3 Correct 629 ms 122672 KB Output is correct
4 Correct 689 ms 125628 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 98156 KB Output is correct
2 Correct 54 ms 98160 KB Output is correct
3 Correct 57 ms 98284 KB Output is correct
4 Correct 54 ms 98156 KB Output is correct
5 Correct 55 ms 98176 KB Output is correct
6 Correct 54 ms 98156 KB Output is correct
7 Correct 54 ms 98168 KB Output is correct
8 Correct 54 ms 98156 KB Output is correct
9 Correct 53 ms 98156 KB Output is correct
10 Correct 53 ms 98156 KB Output is correct
11 Correct 55 ms 98284 KB Output is correct
12 Correct 55 ms 98156 KB Output is correct
13 Correct 54 ms 98212 KB Output is correct
14 Correct 55 ms 98156 KB Output is correct
15 Correct 57 ms 98156 KB Output is correct
16 Correct 53 ms 98156 KB Output is correct
17 Correct 53 ms 98156 KB Output is correct
18 Correct 55 ms 98156 KB Output is correct
19 Correct 54 ms 98156 KB Output is correct
20 Correct 55 ms 98284 KB Output is correct
21 Correct 56 ms 98284 KB Output is correct
22 Correct 58 ms 98156 KB Output is correct
23 Correct 56 ms 98284 KB Output is correct
24 Correct 64 ms 98284 KB Output is correct
25 Correct 55 ms 98284 KB Output is correct
26 Correct 54 ms 98284 KB Output is correct
27 Correct 55 ms 98284 KB Output is correct
28 Correct 55 ms 98284 KB Output is correct
29 Correct 55 ms 98284 KB Output is correct
30 Correct 55 ms 98284 KB Output is correct
31 Correct 55 ms 98284 KB Output is correct
32 Correct 58 ms 98292 KB Output is correct
33 Correct 442 ms 118856 KB Output is correct
34 Correct 430 ms 122184 KB Output is correct
35 Correct 442 ms 129212 KB Output is correct
36 Correct 442 ms 129084 KB Output is correct
37 Correct 392 ms 120388 KB Output is correct
38 Correct 425 ms 121404 KB Output is correct
39 Correct 379 ms 120392 KB Output is correct
40 Correct 413 ms 124220 KB Output is correct
41 Correct 372 ms 120392 KB Output is correct
42 Correct 370 ms 120388 KB Output is correct
43 Correct 395 ms 124612 KB Output is correct
44 Correct 396 ms 124604 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 98188 KB Output is correct
2 Correct 54 ms 98156 KB Output is correct
3 Correct 54 ms 98192 KB Output is correct
4 Correct 55 ms 98156 KB Output is correct
5 Correct 55 ms 98284 KB Output is correct
6 Correct 54 ms 98156 KB Output is correct
7 Correct 61 ms 98284 KB Output is correct
8 Correct 54 ms 98156 KB Output is correct
9 Correct 54 ms 98156 KB Output is correct
10 Correct 55 ms 98284 KB Output is correct
11 Correct 54 ms 98156 KB Output is correct
12 Correct 57 ms 98156 KB Output is correct
13 Correct 54 ms 98156 KB Output is correct
14 Correct 54 ms 98156 KB Output is correct
15 Correct 54 ms 98156 KB Output is correct
16 Correct 61 ms 98156 KB Output is correct
17 Correct 54 ms 98156 KB Output is correct
18 Correct 57 ms 98156 KB Output is correct
19 Correct 54 ms 98156 KB Output is correct
20 Correct 54 ms 98156 KB Output is correct
21 Correct 56 ms 98156 KB Output is correct
22 Correct 54 ms 98156 KB Output is correct
23 Correct 58 ms 98284 KB Output is correct
24 Correct 56 ms 98304 KB Output is correct
25 Correct 55 ms 98260 KB Output is correct
26 Correct 56 ms 98412 KB Output is correct
27 Correct 55 ms 98284 KB Output is correct
28 Correct 55 ms 98284 KB Output is correct
29 Correct 55 ms 98284 KB Output is correct
30 Correct 55 ms 98284 KB Output is correct
31 Correct 54 ms 98284 KB Output is correct
32 Correct 56 ms 98284 KB Output is correct
33 Correct 447 ms 121136 KB Output is correct
34 Correct 710 ms 131504 KB Output is correct
35 Correct 635 ms 122708 KB Output is correct
36 Correct 702 ms 126480 KB Output is correct
37 Correct 429 ms 122300 KB Output is correct
38 Correct 435 ms 122184 KB Output is correct
39 Correct 442 ms 129240 KB Output is correct
40 Correct 468 ms 129060 KB Output is correct
41 Correct 383 ms 120380 KB Output is correct
42 Correct 410 ms 121304 KB Output is correct
43 Correct 377 ms 120380 KB Output is correct
44 Correct 415 ms 124220 KB Output is correct
45 Correct 370 ms 120388 KB Output is correct
46 Correct 372 ms 120392 KB Output is correct
47 Correct 394 ms 124664 KB Output is correct
48 Correct 397 ms 124616 KB Output is correct
49 Correct 675 ms 123968 KB Output is correct
50 Correct 676 ms 123952 KB Output is correct
51 Correct 524 ms 130868 KB Output is correct
52 Correct 543 ms 130224 KB Output is correct
53 Correct 601 ms 122416 KB Output is correct
54 Correct 551 ms 122928 KB Output is correct
55 Correct 512 ms 121252 KB Output is correct
56 Correct 578 ms 125688 KB Output is correct
57 Correct 438 ms 121648 KB Output is correct
58 Correct 464 ms 122160 KB Output is correct
59 Correct 397 ms 124724 KB Output is correct