oj.uz

Submission #851980

# Submission time Handle Problem Language Result Execution time Memory
851980 2023-09-21T02:59:42 Z ntkphong Horses (IOI15_horses) C++14
17 / 100
 555 ms 46056 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
 
const int lim = 1e9; 
const int mod = 1e9 + 7;
const int mxN = 5e5 + 10;
 
int n;
int aX[mxN], aY[mxN];
pair<int, int> ST[mxN << 2];
map<int, int> mp;
 
void update(int node, int l, int r, int x) {
    if(r < x || x < l) return ;
    
    if(l == r) {
        ST[node].first = aX[l];
        ST[node].second = aY[l];
        return ;
    }
    
    int mid = (l + r) / 2;
    update(node * 2, l, mid, x);
    update(node * 2 + 1, mid + 1, r, x);
    
    ST[node].first = 1LL * (ST[node * 2].first * ST[node * 2 + 1].first) % mod;
    ST[node].second = max(ST[node * 2].second, ST[node * 2 + 1].second);
}
 
int get_mul(int node, int l, int r, int x) {
    if(l == r) 
        return ST[node].first;
    
    int mid = (l + r) / 2;
    if(x <= mid) {
        return get_mul(node * 2, l, mid, x);
    } else {
        return 1LL * (ST[node * 2].first * get_mul(node * 2 + 1, mid + 1, r, x)) % mod;
    }
}
 
int get_max(int node, int l, int r, int u, int v) {
    if(r < u || v < l) return 0;
    
    if(u <= l && r <= v) 
        return ST[node].second;
        
    int mid = (l + r) / 2;
    return max(get_max(node * 2, l, mid, u, v), get_max(node * 2 + 1, mid + 1, r, u, v));
}
 
int find_max() {
    long double frmax = aY[n - 1];
    int mul = 1;
    int res = get_mul(1, 0, n - 1, n - 1) * aY[n - 1];
    
    for(auto i = mp.rbegin(); i != mp.rend(); ) {
        int r = i->first;
        r -- ;
        
        if(1LL * mul * aX[i->first] > 1LL * lim) break ;
        mul *= aX[i->first];
        
        i ++ ;
        if(i != mp.rend()) {
            int l = i->first;
            
            if(l > r) continue ;
            
            int x = get_max(1, 0, n - 1, l, r);
            long double frnew = (long double) x / mul;
            
            if(frnew > frmax) {
                frmax = frnew;
                res = 1LL * (get_mul(1, 0, n - 1, l) * x) % mod;
            }
        }
    }
    
    return res;
}
 
int init(int N, int X[], int Y[]) {
    n = N;
    for(int i = 0; i < N; i ++) aX[i] = X[i];
    for(int i = 0; i < N; i ++) aY[i] = Y[i];
    
    mp.insert({0, 1});
    mp.insert({N - 1, 1});
    
    for(int i = 0; i < N; i ++) {
        if(aX[i] > 1) {
            mp.insert({i, 1});
        }
    }
    
    for(int i = 0; i < N; i ++) update(1, 0, N - 1, i);
    
	return find_max();
}
 
int updateX(int pos, int val) {	
    aX[pos] = val;
    update(1, 0, n - 1, pos);
    
    if(pos != n - 1 && pos != 0 && aX[pos] <= 1) {
        if(mp.find(pos) != mp.end()) {
            mp.erase(pos);
        }
    }
    
	return find_max();
}
 
int updateY(int pos, int val) {
	aY[pos] = val;
	update(1, 0, n - 1, pos);
	return find_max();
}

Subtask #1
17.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 4440 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4696 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 4440 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 4440 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 1 ms 4440 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 4440 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Incorrect 1 ms 4440 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 555 ms 46056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 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 4440 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 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 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 4440 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Incorrect 1 ms 4440 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4536 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4432 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4540 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Incorrect 1 ms 4440 KB Output isn't correct
22 Halted 0 ms 0 KB -