oj.uz

답안 #288477

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
288477 2020-09-01T14:16:06 Z amoo_safar 말 (IOI15_horses) C++17
100 / 100
 935 ms 49144 KB 
#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 10;
const int MX = 1e9 + 1;
const int Mod = 1e9 + 7;

ll mul(ll a, ll b){
	return (a * b) % Mod;
}
ll bin_pow(ll b, ll p){
	ll res = 1;
	for(ll j = 1, pw = b; j <= p; j <<= 1, pw = mul(pw, pw))
		if(j & p)
			res = mul(res, pw);
	return res;
}
ll inv(ll x){
	return bin_pow(x, Mod - 2);
}


int n;
set<int> Big;
ll dp[N];
ll X[N], Y[N];

ll fen[N];
void Add(ll idx, ll x){
	idx += 2;
	for(; idx < N; idx += (idx & (-idx)))
		fen[idx] = mul(fen[idx], x);
}
ll Get(ll idx){
	if(idx < 0) return 1;

	idx += 2;
	ll res = 1;
	for(; idx; idx -= (idx & (-idx)))
		res = mul(res, fen[idx]);
	return res;
}

ll seg[N << 2];
void Change(int id, int idx, ll x, int L = 0, int R = N){
	if(L + 1 == R){
		seg[id] = x;
		return ;
	}
	int mid = (L + R) >> 1;
	if(idx < mid)
		Change(id << 1, idx, x, L, mid);
	else 
		Change(id << 1 | 1, idx, x, mid, R);
	seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}
ll Max(int id, int l, int r, int L = 0, int R = N){
	if(r <= L || R <= l) return 0;
	if(l <= L && R <= r) return seg[id];
	int mid = (L + R) >> 1;
	return max(Max(id << 1, l, r, L, mid), Max(id << 1 | 1, l, r, mid, R));
}


ll Calc(){
	dp[n] = 0;
	Big.insert(0);
	int pos, la = n;
	for(auto it = Big.rbegin(); it != Big.rend(); it ++){
		pos = *it;
	//for(int pos = n - 1; pos >= 0; pos --){	
		dp[pos] = X[pos] * max(Max(1, pos, la), dp[la]);
		//dp[pos] = X[pos] * max(Y[pos], dp[la]);
		
		//assert((X[pos] > 1 || pos == 0));
		if(dp[pos] >= MX)
			return mul(dp[pos] % Mod, Get(pos - 1));
		
		la = pos;
	}
	return dp[0] % Mod;
}

int init(int _n, int _X[], int _Y[]) {

	fill(fen, fen + N, 1);
	Big.clear();

	n = _n;
	for(int i = 0; i < n; i++){
		X[i] = _X[i]; Y[i] = _Y[i];
		Change(1, i, Y[i]);
		Add(i, X[i]);
		if(X[i] > 1) Big.insert(i);
	}
	return Calc();
}

int updateX(int pos, int val) {	
	Big.erase(pos);
	Add(pos, mul(inv(X[pos]), val) );
	X[pos] = val;
	if(val > 1)
		Big.insert(pos);
	return Calc();
}

int updateY(int pos, int val) {
	Y[pos] = val;
	Change(1, pos, val);
	return Calc();
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:101:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  101 |  return Calc();
      |         ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:110:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  110 |  return Calc();
      |         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:116:13: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |  return Calc();
      |         ~~~~^~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 2 ms 4352 KB Output is correct
3 Correct 2 ms 4352 KB Output is correct
4 Correct 2 ms 4352 KB Output is correct
5 Correct 3 ms 4352 KB Output is correct
6 Correct 3 ms 4352 KB Output is correct
7 Correct 2 ms 4352 KB Output is correct
8 Correct 2 ms 4352 KB Output is correct
9 Correct 3 ms 4352 KB Output is correct
10 Correct 3 ms 4352 KB Output is correct
11 Correct 3 ms 4352 KB Output is correct
12 Correct 3 ms 4352 KB Output is correct
13 Correct 3 ms 4352 KB Output is correct
14 Correct 3 ms 4352 KB Output is correct
15 Correct 2 ms 4352 KB Output is correct
16 Correct 3 ms 4352 KB Output is correct
17 Correct 3 ms 4352 KB Output is correct
18 Correct 2 ms 4352 KB Output is correct
19 Correct 2 ms 4352 KB Output is correct
20 Correct 3 ms 4352 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4352 KB Output is correct
2 Correct 2 ms 4352 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 3 ms 4352 KB Output is correct
5 Correct 3 ms 4352 KB Output is correct
6 Correct 2 ms 4352 KB Output is correct
7 Correct 3 ms 4352 KB Output is correct
8 Correct 2 ms 4352 KB Output is correct
9 Correct 3 ms 4352 KB Output is correct
10 Correct 3 ms 4352 KB Output is correct
11 Correct 3 ms 4352 KB Output is correct
12 Correct 3 ms 4352 KB Output is correct
13 Correct 3 ms 4352 KB Output is correct
14 Correct 2 ms 4352 KB Output is correct
15 Correct 3 ms 4352 KB Output is correct
16 Correct 3 ms 4352 KB Output is correct
17 Correct 3 ms 4352 KB Output is correct
18 Correct 3 ms 4352 KB Output is correct
19 Correct 3 ms 4352 KB Output is correct
20 Correct 2 ms 4352 KB Output is correct
21 Correct 2 ms 4352 KB Output is correct
22 Correct 3 ms 4352 KB Output is correct
23 Correct 3 ms 4352 KB Output is correct
24 Correct 4 ms 4352 KB Output is correct
25 Correct 5 ms 4352 KB Output is correct
26 Correct 4 ms 4352 KB Output is correct
27 Correct 10 ms 4352 KB Output is correct
28 Correct 5 ms 4352 KB Output is correct
29 Correct 4 ms 4352 KB Output is correct
30 Correct 4 ms 4480 KB Output is correct
31 Correct 7 ms 4352 KB Output is correct
32 Correct 9 ms 4352 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 855 ms 48860 KB Output is correct
2 Correct 447 ms 48836 KB Output is correct
3 Correct 475 ms 48888 KB Output is correct
4 Correct 482 ms 48632 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 2 ms 4352 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 2 ms 4352 KB Output is correct
5 Correct 3 ms 4352 KB Output is correct
6 Correct 3 ms 4352 KB Output is correct
7 Correct 2 ms 4352 KB Output is correct
8 Correct 3 ms 4352 KB Output is correct
9 Correct 3 ms 4352 KB Output is correct
10 Correct 2 ms 4352 KB Output is correct
11 Correct 3 ms 4352 KB Output is correct
12 Correct 3 ms 4352 KB Output is correct
13 Correct 2 ms 4352 KB Output is correct
14 Correct 3 ms 4480 KB Output is correct
15 Correct 3 ms 4352 KB Output is correct
16 Correct 4 ms 4352 KB Output is correct
17 Correct 2 ms 4352 KB Output is correct
18 Correct 3 ms 4352 KB Output is correct
19 Correct 3 ms 4352 KB Output is correct
20 Correct 3 ms 4352 KB Output is correct
21 Correct 3 ms 4352 KB Output is correct
22 Correct 3 ms 4352 KB Output is correct
23 Correct 3 ms 4352 KB Output is correct
24 Correct 4 ms 4352 KB Output is correct
25 Correct 5 ms 4352 KB Output is correct
26 Correct 4 ms 4352 KB Output is correct
27 Correct 9 ms 4352 KB Output is correct
28 Correct 5 ms 4352 KB Output is correct
29 Correct 4 ms 4352 KB Output is correct
30 Correct 4 ms 4480 KB Output is correct
31 Correct 7 ms 4352 KB Output is correct
32 Correct 9 ms 4352 KB Output is correct
33 Correct 136 ms 24440 KB Output is correct
34 Correct 131 ms 24448 KB Output is correct
35 Correct 286 ms 47864 KB Output is correct
36 Correct 271 ms 47836 KB Output is correct
37 Correct 208 ms 24824 KB Output is correct
38 Correct 196 ms 36216 KB Output is correct
39 Correct 132 ms 24184 KB Output is correct
40 Correct 261 ms 47864 KB Output is correct
41 Correct 159 ms 24312 KB Output is correct
42 Correct 181 ms 24256 KB Output is correct
43 Correct 249 ms 47736 KB Output is correct
44 Correct 249 ms 47736 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4352 KB Output is correct
2 Correct 2 ms 4352 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 3 ms 4352 KB Output is correct
5 Correct 2 ms 4352 KB Output is correct
6 Correct 3 ms 4352 KB Output is correct
7 Correct 3 ms 4352 KB Output is correct
8 Correct 3 ms 4352 KB Output is correct
9 Correct 2 ms 4352 KB Output is correct
10 Correct 2 ms 4352 KB Output is correct
11 Correct 3 ms 4352 KB Output is correct
12 Correct 3 ms 4352 KB Output is correct
13 Correct 3 ms 4352 KB Output is correct
14 Correct 2 ms 4352 KB Output is correct
15 Correct 3 ms 4352 KB Output is correct
16 Correct 2 ms 4352 KB Output is correct
17 Correct 2 ms 4352 KB Output is correct
18 Correct 3 ms 4352 KB Output is correct
19 Correct 3 ms 4352 KB Output is correct
20 Correct 3 ms 4352 KB Output is correct
21 Correct 2 ms 4352 KB Output is correct
22 Correct 3 ms 4352 KB Output is correct
23 Correct 4 ms 4352 KB Output is correct
24 Correct 4 ms 4352 KB Output is correct
25 Correct 5 ms 4352 KB Output is correct
26 Correct 4 ms 4352 KB Output is correct
27 Correct 9 ms 4352 KB Output is correct
28 Correct 6 ms 4480 KB Output is correct
29 Correct 4 ms 4352 KB Output is correct
30 Correct 4 ms 4480 KB Output is correct
31 Correct 7 ms 4352 KB Output is correct
32 Correct 9 ms 4352 KB Output is correct
33 Correct 852 ms 48632 KB Output is correct
34 Correct 441 ms 48760 KB Output is correct
35 Correct 474 ms 48632 KB Output is correct
36 Correct 493 ms 48632 KB Output is correct
37 Correct 138 ms 24440 KB Output is correct
38 Correct 131 ms 24440 KB Output is correct
39 Correct 290 ms 47800 KB Output is correct
40 Correct 276 ms 47864 KB Output is correct
41 Correct 212 ms 24824 KB Output is correct
42 Correct 196 ms 36216 KB Output is correct
43 Correct 127 ms 24192 KB Output is correct
44 Correct 257 ms 47864 KB Output is correct
45 Correct 161 ms 24312 KB Output is correct
46 Correct 178 ms 24312 KB Output is correct
47 Correct 253 ms 47864 KB Output is correct
48 Correct 245 ms 47752 KB Output is correct
49 Correct 257 ms 26448 KB Output is correct
50 Correct 230 ms 26432 KB Output is correct
51 Correct 454 ms 48760 KB Output is correct
52 Correct 334 ms 48632 KB Output is correct
53 Correct 935 ms 26860 KB Output is correct
54 Correct 383 ms 39288 KB Output is correct
55 Correct 265 ms 24440 KB Output is correct
56 Correct 375 ms 49144 KB Output is correct
57 Correct 569 ms 25208 KB Output is correct
58 Correct 810 ms 25336 KB Output is correct
59 Correct 256 ms 47736 KB Output is correct