oj.uz

Submission #956365

# Submission time Handle Problem Language Result Execution time Memory
956365 2024-04-01T17:20:45 Z steveonalex Horses (IOI15_horses) C++17
100 / 100
 352 ms 56896 KB 
#include <bits/stdc++.h>
#include "horses.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int MOD = 1e9 + 7, N = 5e5 + 69;
int n;
vector<int> X, Y;

struct SegmentTreeProd{
    int n;
    vector<ll> a;

    SegmentTreeProd(int _n){
        n = _n;
        a.resize(n * 2 + 2, 1);
    }

    void update(int i, int v){
        i += n; a[i] = v;
        while(i > 1){
            i >>= 1;
            a[i] = a[i * 2] * a[i * 2 + 1] % MOD;
        }
    }

    ll get(int l, int r){
        l += n; r += n + 1;
        ll ans =1;
        while(l < r){
            if (l & 1) ans = ans * a[l++] % MOD;
            if (r & 1) ans = ans * a[--r] % MOD;
            l >>= 1; r >>= 1;
        }
        return ans;
    }
};


struct SegmentTreeMax{
    int n;
    vector<int> a;

    SegmentTreeMax(int _n){
        n = _n;
        a.resize(n * 2 + 2, 0);
    }

    void update(int i, int v){
        i += n; a[i] = v;
        while(i > 1){
            i >>= 1;
            a[i] = max(a[i * 2], a[i * 2 + 1]);
        }
    }

    ll get(int l, int r){
        l += n; r += n + 1;
        int ans = 0;
        while(l < r){
            if (l & 1) maximize(ans, a[l++]);
            if (r & 1) maximize(ans, a[--r]);
            l >>= 1; r >>= 1;
        }
        return ans;
    }
};

SegmentTreeProd st1(N);
SegmentTreeMax st2(N);

set<int> S; 

int calc(){
    if (S.size() == 0) return st2.get(1, n);
    ll mul = 1;
    auto it = S.end(); it--;
    vector<pair<int, int>> chode;
    while(true){
        chode.push_back({*it, X[*it]});
        mul *= chode.back().second;
        if (mul > 1e9){
            break;
        }
        else if (it == S.begin()) {
            if (chode.back().first != 1) chode.push_back({1, 1});
            break;
        }
        it--;
    }

    ll sugma = st1.get(1, chode.back().first - 1);
    reverse(ALL(chode));
    mul = 1;
    __int128 ans = 0;
    for(pair<int, int> i: chode){
        mul = mul * i.second;
        __int128 tmp = mul;
        tmp *= st2.get(i.first, n);
        maximize(ans, tmp);
    }
    ans %= MOD;
    return sugma * ans % MOD;
}

int init(int _n, int x[], int y[]) {
    n = _n;
    X.resize(n+1); Y.resize(n+1);
    for(int i = 0; i<n; ++i) X[i+1] = x[i];
    for(int i = 0; i<n; ++i) Y[i+1] = y[i];
        
    for(int i= 1; i<=n; ++i) st1.update(i, X[i]);
    for(int i= 1; i<=n; ++i) st2.update(i, Y[i]);

    for(int i = 1; i<=n; ++i) if (X[i] > 1) S.insert(i);

    return calc();
}

int updateX(int pos, int val) { 
    pos++;
    if (X[pos] > 1){
        S.erase(pos);
    }
    X[pos] = val;
    if (X[pos] > 1) S.insert(pos);

    st1.update(pos, val);

    return calc();
}

int updateY(int pos, int val) {
    pos++;
    st2.update(pos, val);
    Y[pos] = val;
    return calc();
}


// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int x[] = {2, 1, 3}, y[] = {3, 4, 1};
//     cout << init(3, x, y) << "\n";
//     cout << updateY(1, 2) << "\n";

//     return 0;
// }

Compilation message

horses.cpp: In function 'int calc()':
horses.cpp:117:38: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  117 |     if (S.size() == 0) return st2.get(1, n);
      |                               ~~~~~~~^~~~~~
horses.cpp:124:13: warning: conversion from 'll' {aka 'long long int'} to 'double' may change value [-Wconversion]
  124 |         if (mul > 1e9){
      |             ^~~
horses.cpp:145:24: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  145 |     return sugma * ans % MOD;
      |            ~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 4 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 3 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 4 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 3 ms 12124 KB Output is correct
14 Correct 3 ms 12124 KB Output is correct
15 Correct 3 ms 12124 KB Output is correct
16 Correct 3 ms 12124 KB Output is correct
17 Correct 3 ms 12124 KB Output is correct
18 Correct 3 ms 12124 KB Output is correct
19 Correct 3 ms 12124 KB Output is correct
20 Correct 4 ms 12124 KB Output is correct
21 Correct 3 ms 12324 KB Output is correct
22 Correct 4 ms 12124 KB Output is correct
23 Correct 4 ms 12120 KB Output is correct
24 Correct 4 ms 12124 KB Output is correct
25 Correct 4 ms 12124 KB Output is correct
26 Correct 4 ms 12124 KB Output is correct
27 Correct 5 ms 12380 KB Output is correct
28 Correct 4 ms 12120 KB Output is correct
29 Correct 4 ms 12124 KB Output is correct
30 Correct 4 ms 12124 KB Output is correct
31 Correct 4 ms 12212 KB Output is correct
32 Correct 4 ms 12124 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 44424 KB Output is correct
2 Correct 303 ms 56868 KB Output is correct
3 Correct 283 ms 48212 KB Output is correct
4 Correct 352 ms 52048 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 4 ms 12048 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 3 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 3 ms 12124 KB Output is correct
10 Correct 3 ms 12028 KB Output is correct
11 Correct 3 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 3 ms 12124 KB Output is correct
14 Correct 3 ms 12124 KB Output is correct
15 Correct 3 ms 12120 KB Output is correct
16 Correct 3 ms 12120 KB Output is correct
17 Correct 3 ms 12120 KB Output is correct
18 Correct 3 ms 12120 KB Output is correct
19 Correct 3 ms 12124 KB Output is correct
20 Correct 3 ms 12116 KB Output is correct
21 Correct 3 ms 12124 KB Output is correct
22 Correct 3 ms 11996 KB Output is correct
23 Correct 4 ms 12124 KB Output is correct
24 Correct 4 ms 12120 KB Output is correct
25 Correct 5 ms 12380 KB Output is correct
26 Correct 4 ms 12124 KB Output is correct
27 Correct 5 ms 12120 KB Output is correct
28 Correct 4 ms 12124 KB Output is correct
29 Correct 4 ms 12204 KB Output is correct
30 Correct 4 ms 12124 KB Output is correct
31 Correct 4 ms 12124 KB Output is correct
32 Correct 4 ms 12124 KB Output is correct
33 Correct 95 ms 23960 KB Output is correct
34 Correct 94 ms 24124 KB Output is correct
35 Correct 202 ms 54348 KB Output is correct
36 Correct 210 ms 54240 KB Output is correct
37 Correct 97 ms 22100 KB Output is correct
38 Correct 131 ms 34896 KB Output is correct
39 Correct 85 ms 21848 KB Output is correct
40 Correct 192 ms 49492 KB Output is correct
41 Correct 88 ms 22284 KB Output is correct
42 Correct 91 ms 22096 KB Output is correct
43 Correct 184 ms 49748 KB Output is correct
44 Correct 184 ms 49708 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 4 ms 12120 KB Output is correct
3 Correct 3 ms 12120 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12124 KB Output is correct
6 Correct 3 ms 12112 KB Output is correct
7 Correct 3 ms 12124 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 3 ms 12120 KB Output is correct
10 Correct 3 ms 12124 KB Output is correct
11 Correct 3 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 3 ms 12124 KB Output is correct
14 Correct 3 ms 12124 KB Output is correct
15 Correct 3 ms 12060 KB Output is correct
16 Correct 3 ms 11976 KB Output is correct
17 Correct 4 ms 12124 KB Output is correct
18 Correct 3 ms 12124 KB Output is correct
19 Correct 3 ms 12136 KB Output is correct
20 Correct 3 ms 12116 KB Output is correct
21 Correct 3 ms 12120 KB Output is correct
22 Correct 4 ms 12124 KB Output is correct
23 Correct 4 ms 12124 KB Output is correct
24 Correct 4 ms 12124 KB Output is correct
25 Correct 5 ms 12164 KB Output is correct
26 Correct 4 ms 12124 KB Output is correct
27 Correct 5 ms 12252 KB Output is correct
28 Correct 4 ms 12124 KB Output is correct
29 Correct 4 ms 12124 KB Output is correct
30 Correct 5 ms 12124 KB Output is correct
31 Correct 4 ms 12124 KB Output is correct
32 Correct 4 ms 12204 KB Output is correct
33 Correct 282 ms 48064 KB Output is correct
34 Correct 302 ms 56896 KB Output is correct
35 Correct 285 ms 48208 KB Output is correct
36 Correct 346 ms 52304 KB Output is correct
37 Correct 94 ms 24132 KB Output is correct
38 Correct 93 ms 24148 KB Output is correct
39 Correct 208 ms 54608 KB Output is correct
40 Correct 203 ms 54356 KB Output is correct
41 Correct 96 ms 22260 KB Output is correct
42 Correct 133 ms 35412 KB Output is correct
43 Correct 84 ms 22064 KB Output is correct
44 Correct 198 ms 49488 KB Output is correct
45 Correct 86 ms 22100 KB Output is correct
46 Correct 91 ms 22020 KB Output is correct
47 Correct 199 ms 49652 KB Output is correct
48 Correct 192 ms 49748 KB Output is correct
49 Correct 143 ms 27176 KB Output is correct
50 Correct 141 ms 26964 KB Output is correct
51 Correct 270 ms 56404 KB Output is correct
52 Correct 239 ms 55636 KB Output is correct
53 Correct 221 ms 25348 KB Output is correct
54 Correct 193 ms 38992 KB Output is correct
55 Correct 125 ms 23008 KB Output is correct
56 Correct 253 ms 51468 KB Output is correct
57 Correct 148 ms 23636 KB Output is correct
58 Correct 183 ms 24220 KB Output is correct
59 Correct 196 ms 49952 KB Output is correct