oj.uz

Submission #795458

# Submission time Handle Problem Language Result Execution time Memory
795458 2023-07-27T10:03:03 Z Markynoodle Horses (IOI15_horses) C++17
17 / 100
 331 ms 105204 KB 
#include "horses.h"
#include<bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()
#define ll long long
#define fastOI ios_base::sync_with_stdio(false); cin.tie(nullptr);
auto cmp = [](int a, int b){return a > b;};
auto cmp1 = [](pair<ll,ll> a, pair<ll,ll> b){return a.second < b.second;};
ll mod = 1000000007;


vector<ll> segtreex;
vector<ll> segtreey;

void updatex(int l, int r, int pos, int ind, ll x){

    int m = l + (r - l)/2;
    if(ind < l || ind >= r)return;
    if(l == ind && l + 1 == r){
        segtreex[pos] = x;
        return;
    }
    updatex(l, m, pos*2, ind, x);
    updatex(m, r, pos*2 + 1, ind, x);
    segtreex[pos] = (segtreex[pos*2] * segtreex[pos*2 + 1])%mod;
    return;
}

ll queryx(int l, int r, int pos, int ql, int qr){
    if( ql <= l && qr >= r)return segtreex[pos];
    if( qr <= l || ql >= r)return 1;
    int m = l + (r-l)/2;
    return (queryx(l, m, pos * 2, ql, qr) * queryx(m, r, pos*2 + 1, ql, qr))%mod;
}

void updatey(int l, int r, int pos, int ind, ll x){
    int m = l + (r - l)/2;
    if(ind < l || ind >= r)return;
    if(l == ind && l + 1 == r){
        segtreey[pos] = x;
        return;
    }
    updatey(l, m, pos*2, ind, x);
    updatey(m, r, pos*2 + 1, ind, x);
    segtreey[pos] = max(segtreey[pos*2], segtreey[pos*2 + 1]);
    return;
}

ll queryy(int l, int r, int pos, int ql, int qr){

    if( ql <= l && qr >= r)return segtreey[pos];
    if( qr <= l || ql >= r)return 0;
    int m = l + (r-l)/2;
    return max(queryy(l, m, pos * 2, ql, qr), queryy(m, r, pos*2 + 1, ql, qr));
}

set<ll> fasts;
int npo2;
vector<ll> g;
vector<ll> p;
int n;

int solve(){

    if(fasts.empty()){
        return queryy(0, npo2, 1, 0, npo2);
    }
    vector<pair<ll,ll>> solver(30,{1, 1});
    set<ll>::iterator pt = fasts.end();
    int opt = (min(30, int(fasts.size())));
    int last = n;
    ll temppro = 1;
    for(int i = 0 ;i < opt; i++){
        pt--;
        solver[opt - i].first = g[*pt]; // if need be -1 on index
        solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
        //cout<<g[*pt]<<" "<<*pt<<" "<<last<<" "<<solver[opt - i].second<<"\n";
        last = *pt;
        temppro *= g[*pt];
        if(temppro >= mod)break;
    }
    ll startproduct = queryx(0, npo2, 1, 0, last);
    temppro = 1;
    ll best = 1;
    for(int i = 0; i <= opt; i++){
        temppro *= solver[i].first;
        //cout<<temppro<<" "<<temppro * solver[i].second<<"_ ";
        best = max(best, temppro * solver[i].second);
    }
    best %= mod;
    return (best * startproduct)%mod;

    //x for growth
    // y for prices;
}
int init(int nn, int xx[], int yy[]){
    for(int i = 0; i<nn; i++){
        g.push_back(xx[i]);
        p.push_back(yy[i]);
    }

    n = nn;
    npo2 = __lg(n-1) + 1;
    npo2 = (1<<npo2);
    segtreex.resize(npo2 * 2, 1);
    segtreey.resize(npo2 * 2, 0);
    for(int i = 0; i<n; i++){
        if(g[i] > 1){
            updatex(0, npo2, 1, i, g[i]);
        }
        if(g[i] > 1)fasts.insert(i);
    }
    for(int i = 0; i<n; i++){
        updatey(0, npo2, 1, i, p[i]);
    }
    return solve();
}




int updateX(int pos, int val) {	
    updatex(0, npo2, 1, pos, val);
    if(val == 1){
        fasts.erase(val);
    }
    else fasts.insert(val);
    g[pos] = val;
	return solve();
}

int updateY(int pos, int val) {
    updatey(0, npo2, 1, pos, val);
    p[pos] = val;
	return solve();
}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:67:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   67 |         return queryy(0, npo2, 1, 0, npo2);
      |                ~~~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp:77:53: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   77 |         solver[opt - i].second = queryy(0, npo2, 1, *pt, last);
      |                                                     ^~~
horses.cpp:79:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |         last = *pt;
      |                ^~~
horses.cpp:92:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   92 |     return (best * startproduct)%mod;
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 1 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 0 ms 212 KB Output is correct

Subtask #2
0 / 17.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 0 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 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 0 ms 212 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 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 Runtime error 1 ms 340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 331 ms 105204 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory 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 1 ms 212 KB Output is correct
12 Correct 0 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 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
21 Runtime error 1 ms 340 KB Execution killed with signal 11
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 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 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 Runtime error 1 ms 340 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -