oj.uz

답안 #599101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
599101 2022-07-19T10:05:18 Z Temmie 말 (IOI15_horses) C++17
17 / 100
 509 ms 37912 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 * sfmx > (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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 240 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 1 ms 280 KB Output is correct
13 Correct 1 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 1 ms 212 KB Output is correct
17 Correct 0 ms 296 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
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 1 ms 300 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 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 0 ms 296 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 300 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 296 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 296 KB Output is correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 509 ms 37912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 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 1 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 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 1 ms 212 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 1 ms 296 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Incorrect 1 ms 352 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 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 1 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 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 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 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 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Incorrect 1 ms 340 KB Output isn't correct
24 Halted 0 ms 0 KB -