oj.uz

Submission #832946

# Submission time Handle Problem Language Result Execution time Memory
832946 2023-08-21T17:01:53 Z happypotato Horses (IOI15_horses) C++17
17 / 100
 1500 ms 45900 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
const int MOD = 1e9 + 7;
int bigmod(int b, int p) {
	b %= MOD;
	int res = 1;
	while (p) {
		if (p & 1) res = (res * b) % MOD;
		p >>= 1; b = (b * b) % MOD;
	}
	return res;
}
int modinv(int x) {
	return bigmod(x, MOD - 2);
}
const int mxN = 5e5 + 1;
int seg[4 * mxN];
pii a[mxN];
int n;
void build(int l = 1, int r = n, int idx = 1) {
	if (l == r) {
		seg[idx] = a[l].ss;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, (idx << 1));
	build(mid + 1, r, (idx << 1) | 1);
	seg[idx] = max(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
void update(int pos, int val, int l = 1, int r = n, int idx = 1) {
	if (l == r) {
		seg[idx] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) update(pos, val, l, mid, (idx << 1));
	else update(pos, val, mid + 1, r, (idx << 1) | 1);
	seg[idx] = max(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
int query(int tl, int tr, int l = 1, int r = n, int idx = 1) {
	if (tl <= l && r <= tr) return seg[idx];
	int mid = (l + r) >> 1;
	int res = -1e9;
	if (tl <= mid) res = max(res, query(tl, tr, l, mid, (idx << 1)));
	if (tr > mid) res = max(res, query(tl, tr, mid + 1, r, (idx << 1) | 1));
	return res;
}
set<int> s;
int totmult = 1;

int findans() {
	int multi = 1;
	int res = 0;
	set<int>::iterator it = s.end();
	while (res <= (int)(1.5e9) && it != s.begin()) {
		--it;
		res = (max(res, query(*it, n)) * a[*it].ff) % MOD;
		multi *= a[*it].ff;
	}
	if (it == s.begin()) res = max(res, query(1, n));
	res = (res * modinv(multi)) % MOD;
	res = (res * totmult) % MOD;
	return res;
}

int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
	n = N;
	for (int i = 1; i <= n; i++) {
		a[i] = {X[i - 1], Y[i - 1]};
		if (a[i].ff >= 2) {
			s.insert(i);
			totmult = (totmult * a[i].ff) % MOD;
		}
	}
	build();
	return findans();
}

int32_t updateX(int32_t pos, int32_t val) {	
	pos++;
	if (a[pos].ff >= 2) {
		s.erase(s.find(pos));
		totmult = (totmult * modinv(a[pos].ff)) % MOD;
	}
	a[pos].ff = val;
	if (a[pos].ff >= 2) {
		s.insert(pos);
		totmult = (totmult * a[pos].ff) % MOD;
	}
	return findans();
}

int32_t updateY(int32_t pos, int32_t val) {
	pos++;
	a[pos].ss = val;
	update(pos, val);
	return findans();
}

#undef int

Compilation message

horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:81:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
   81 |  return findans();
      |         ~~~~~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:95:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
   95 |  return findans();
      |         ~~~~~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:102:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  102 |  return findans();
      |         ~~~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 312 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 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 292 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 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 1 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 316 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 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 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 Incorrect 0 ms 312 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1576 ms 45900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory 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 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 0 ms 212 KB Output is correct
9 Correct 0 ms 312 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 312 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 1 ms 308 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 312 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 312 KB Output is correct
7 Correct 0 ms 308 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 308 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 312 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 Incorrect 0 ms 308 KB Output isn't correct
22 Halted 0 ms 0 KB -