oj.uz

답안 #599093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
599093 2022-07-19T10:02:41 Z Temmie 말 (IOI15_horses) C++17
17 / 100
 1500 ms 35720 KB 
#include <bits/stdc++.h>

struct Seg_max {
	
	int size;
	std::vector <int> v;
	
	Seg_max(int s) {
		size = 1;
		while (size < s) {
			size <<= 1;
		}
		v.resize(size << 1, 0);
	}
	
	void update(int ind, int val) {
		update(ind, val, 0, 0, size);
	}
	
	void update(int ind, int val, int now, int l, int r) {
		if (!(r - l - 1)) {
			v[now] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if (ind < mid) {
			update(ind, val, now * 2 + 1, l, mid);
		} else {
			update(ind, val, now * 2 + 2, mid, r);
		}
		v[now] = std::max(v[now * 2 + 1], v[now * 2 + 2]);
	}
	
	int query(int l, int r) {
		return query(l, r, 0, 0, size);
	}
	
	int query(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return 0;
		}
		if (l >= tl && r <= tr) {
			return v[now];
		}
		int mid = (l + r) >> 1;
		return std::max(query(tl, tr, now * 2 + 1, l, mid), query(tl, tr, now * 2 + 2, mid, r));
	}
	
};

constexpr const int mod = 1e9 + 7;

int pw(int x, int p) {
	int res = 1;
	while (p) {
		if (p & 1) {
			res = (long long) res * x % mod;
		}
		p >>= 1;
		x = (long long) x * x % mod;
	}
	return res;
}

int inv(int val) {
	return pw(val, mod - 2);
}

int dv(int nu, int de) {
	nu %= mod;
	de %= mod;
	return (long long) nu * inv(de) % mod;
}

int n;
std::vector <int> gr, pr;
Seg_max seg_max(0);
std::set <int> st;

int tot_gr;

int get() {
	st.insert(0);
	for (int i = 0; i < n; i++) st.insert(i); // temp
	long long gr_div = 1;
	int res = (long long) tot_gr * pr[n - 1] % mod;
	int last_sfmx = 0;
	for (auto it = st.rbegin(); it != st.rend(); it++) {
		int ind = *it;
		int sfmx = seg_max.query(ind, n);
		if (sfmx >= gr_div * last_sfmx) {
			res = (long long) dv(tot_gr, gr_div) * sfmx % mod;
		}
		//if (res <= (long long) dv(tot_gr, gr_div) * sfmx % mod) {
			//res = (long long) dv(tot_gr, gr_div) * sfmx % mod;
		//}
		last_sfmx = sfmx;
		gr_div *= gr[ind];
		if (gr_div > (1LL << 30)) {
			break;
		}
	}
	return res;
}

int init(int _n, int _gr[], int _pr[]) {
	n = _n;
	gr.resize(n);
	pr.resize(n);
	seg_max = Seg_max(n);
	tot_gr = 1;
	for (int i = 0; i < n; i++) {
		gr[i] = _gr[i];
		pr[i] = _pr[i];
		if (gr[i] > 1) st.insert(i);
		seg_max.update(i, pr[i]);
		tot_gr = (long long) tot_gr * gr[i] % mod;
	}
	return get();
}

// gr
int updateX(int pos, int val) {
	tot_gr = dv(tot_gr, gr[pos]);
	tot_gr = (long long) tot_gr * (gr[pos] = val) % mod;
	st.erase(pos);
	if (gr[pos] > 1) st.insert(pos);
	return get();
}

// pr
int updateY(int pos, int val) {
	seg_max.update(pos, pr[pos] = val);
	return get();
}

Compilation message

horses.cpp: In function 'int pw(int, int)':
horses.cpp:57:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   57 |    res = (long long) res * x % mod;
      |          ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:60:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   60 |   x = (long long) x * x % mod;
      |       ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int dv(int, int)':
horses.cpp:72:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   72 |  return (long long) nu * inv(de) % mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int get()':
horses.cpp:86:43: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   86 |  int res = (long long) tot_gr * pr[n - 1] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:92:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |    res = (long long) dv(tot_gr, gr_div) * sfmx % mod;
      |                                 ^~~~~~
horses.cpp:92:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |    res = (long long) dv(tot_gr, gr_div) * sfmx % mod;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:117:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  117 |   tot_gr = (long long) tot_gr * gr[i] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:125:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  125 |  tot_gr = (long long) tot_gr * (gr[pos] = val) % mod;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 39 ms 376 KB Output is correct
24 Correct 27 ms 340 KB Output is correct
25 Correct 25 ms 396 KB Output is correct
26 Correct 24 ms 392 KB Output is correct
27 Incorrect 46 ms 384 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1591 ms 35720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 35 ms 340 KB Output is correct
24 Correct 28 ms 396 KB Output is correct
25 Correct 27 ms 404 KB Output is correct
26 Correct 23 ms 404 KB Output is correct
27 Incorrect 46 ms 384 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 224 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 43 ms 384 KB Output is correct
24 Correct 30 ms 340 KB Output is correct
25 Correct 38 ms 312 KB Output is correct
26 Correct 32 ms 404 KB Output is correct
27 Incorrect 50 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -