oj.uz

Submission #876081

# Submission time Handle Problem Language Result Execution time Memory
876081 2023-11-21T08:22:41 Z Elvin_Fritl Horses (IOI15_horses) C++17
37 / 100
 421 ms 55024 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 5e5 + 545 , inf = 1e9 + 12 , mod = 1e9 + 7;

    #include "horses.h"

 
struct segtree {
	int tree[N*4];
	void update(int v,int l,int r,int pos,int val) {
		if(l == r) {
			tree[v] = val; 
			return;
		}
		int mid = (l+r)/2;
		if(pos <= mid) {
			update((v*2), l, mid, pos, val);
		}
		else {
			update((v*2 + 1), mid + 1, r, pos, val);
		}
		tree[v] = max(tree[(v*2)], tree[(v*2 + 1)]);
	}
	int get(int v,int l,int r,int ml,int mr) {
		if(mr < l || r < ml || l > r){
			return 0LL;
		}
		if(ml <= l && r <= mr){
			return tree[v];
		}
		int mid = (l+r)/2;
		return max(get((v*2), l, mid, ml, mr), get((v*2 + 1), mid + 1, r, ml, mr));
	}
	
};
int n;
ll x[N] , y[N];
set<int> s;
ll tmp = 1;
 
ll bp(ll x,ll m){
    if(m == 0){
        return 1LL;
    }
    if(m == 1){
        return x%mod;
    }
    if(m%2==0){
        return bp(x*x%mod,m/2)%mod;
    }
    return x*bp(x,m-1)%mod;
}

segtree S;


int calc() {
	ll res = 1 , ind = -1;
	assert((int)s.size() >= 2);
	auto it = next(s.rbegin());
	while(it != s.rend()) {
		res *= x[*it];
		ind = *it;
		if(res > inf){
			break;
		}
		it = next(it);
	}
	auto it2 = s.lower_bound(ind);
	ll mx = 0; 
	res = 1;
	while(next(it2) != s.end()) {
		int i = *it2;
		int j = *(next(it2));
		if(i != ind){
			res = res*x[i];
		}
		ll ans = S.get(1, 0, n-1, i, j-1);
		mx = max(mx, res*ans);
		it2 = next(it2);
	}
	mx %= mod;
	return tmp*bp(res,mod-2)%mod*mx%mod;
}


int init(int nn, int X[], int Y[]) {
	n = nn;
	for(int i=0;i<n;i++) {
		x[i] = X[i];
		y[i] = Y[i];
	}
	for(int i=0;i<n;i++) {
		S.update(1, 0, n - 1, i, y[i]);
	}
	s.insert(0);
	s.insert(n);
	for(int i=n-1;i>=0;i--) {
		if(x[i] > 1) {
			tmp = (tmp * x[i])%mod;
			s.insert(i); 
		}
	}
	return calc();
}
 
 
int updateX(int pos, int val) {
	tmp = (tmp * bp(x[pos], mod-2))%mod;
	x[pos] = val;
	tmp = (tmp*val)%mod;
	if(val > 1 || pos == 0){
		s.insert(pos);
	}
	else{
		assert(s.find(pos) != s.end());
		s.erase(pos);
	}
	return calc();
}
 
int updateY(int pos, int val) {
	S.update(1, 0, n-1, pos, val);
	return calc();
}

Compilation message

horses.cpp: In function 'll bp(ll, ll)':
horses.cpp:44:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   44 | ll bp(ll x,ll m){
      |       ~~~^
horses.cpp:40:4: note: shadowed declaration is here
   40 | ll x[N] , y[N];
      |    ^
horses.cpp: In function 'int calc()':
horses.cpp:72:27: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::key_type' {aka 'int'} may change value [-Wconversion]
   72 |  auto it2 = s.lower_bound(ind);
      |                           ^~~
horses.cpp:86:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   86 |  return tmp*bp(res,mod-2)%mod*mx%mod;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   97 |   S.update(1, 0, n - 1, i, y[i]);
      |                            ~~~^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4552 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4548 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4528 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Runtime error 5 ms 8796 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 42324 KB Output is correct
2 Correct 297 ms 55024 KB Output is correct
3 Correct 282 ms 46196 KB Output is correct
4 Correct 329 ms 49964 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Runtime error 5 ms 8796 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4544 KB Output is correct
4 Correct 1 ms 4548 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4548 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4544 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4452 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Runtime error 4 ms 8796 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -