oj.uz

Submission #1005353

# Submission time Handle Problem Language Result Execution time Memory
1005353 2024-06-22T10:56:10 Z rahidilbayramli Horses (IOI15_horses) C++17
100 / 100
 452 ms 53416 KB 
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
#include "horses.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9+7, sz = 5e5+5;
const ll inf = 2e9;
int x[sz], y[sz], n;
pii segtree[4*sz];
set<pii>st;
int m(ll x, int y)
{
    return ((x % mod) * y) % mod;
}
void build(int v, int l, int r)
{
    if(l == r)
    {
        segtree[v].f = x[l];
        segtree[v].s = y[l];
    }
    else
    {
        int mid = (l + r) / 2;
        build(2*v, l, mid);
        build(2*v+1, mid+1, r);
        segtree[v].f = m(segtree[2*v].f, segtree[2*v+1].f);
        segtree[v].s = max(segtree[2*v].s, segtree[2*v+1].s);
    }
}
void update(int v, int l, int r, int type, int pos, int val)
{
    if(l == r)
    {
        if(type == 1)
            segtree[v].f = val;
        else
            segtree[v].s = val;
    }
    else
    {
        int mid = (l + r) / 2;
        if(pos <= mid)
            update(2*v, l, mid, type, pos, val);
        else
            update(2*v+1, mid+1, r, type, pos, val);
        segtree[v].f = m(segtree[2*v].f, segtree[2*v+1].f);
        segtree[v].s = max(segtree[2*v].s, segtree[2*v+1].s);
    }
}
pii findans(int v, int l, int r, int tl, int tr)
{
    if(tl > tr)
        return {1, INT_MIN};
    if(l == tl && r == tr)
        return segtree[v];
    else
    {
        int mid = (l + r) / 2;
        pii lans, rans, ans;
        lans = findans(2*v, l, mid, tl, min(mid, tr));
        rans = findans(2*v+1, mid+1, r, max(mid+1, tl), tr);
        ans.f = m(lans.f, rans.f);
        ans.s = max(lans.s, rans.s);
        return ans;
    }
}
int ans()
{
    ll res = 1;
    int lst = n + 1;
    for(auto u : st)
    {
        res = max(res, (ll)(findans(1, 1, n, -u.f, lst-1).s));
        res *= u.s;
        if(res >= inf)
            return m(res, findans(1, 1, n, 1, -u.f-1).f);
        lst = -u.f;
    }
    return res % mod;
}
int init(int N, int X[], int Y[]) {
    n = N;
    for(int i = 1; i <= N; i++)
    {
        x[i] = X[i-1];
        y[i] = Y[i-1];
        if(x[i] >= 2 || i == 1)
            st.insert({-i, x[i]});
    }
    build(1, 1, N);
    return ans();
}
int updateX(int pos, int val) {
    pos++;
    update(1, 1, n, 1, pos, val);
    if(x[pos] >= 2 || pos == 1)
    {
        if(st.find({-pos, x[pos]}) != st.end())
            st.erase({-pos, x[pos]});
    }
    x[pos] = val;
    if(x[pos] >= 2 || pos == 1)
        st.insert({-pos, x[pos]});
    return ans();
}
int updateY(int pos, int val) {
    update(1, 1, n, 2, pos+1, val);
    return ans();
}

Compilation message

horses.cpp: In function 'int m(long long int, int)':
horses.cpp:27:17: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   27 | int m(ll x, int y)
      |             ~~~~^
horses.cpp:24:12: note: shadowed declaration is here
   24 | int x[sz], y[sz], n;
      |            ^
horses.cpp:27:10: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   27 | int m(ll x, int y)
      |          ^
horses.cpp:24:5: note: shadowed declaration is here
   24 | int x[sz], y[sz], n;
      |     ^
horses.cpp:29:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   29 |     return ((x % mod) * y) % mod;
      |            ~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int ans()':
horses.cpp:96:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |     return res % mod;
      |            ~~~~^~~~~

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 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 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 4444 KB Output is correct
18 Correct 0 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct

Subtask #2
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 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 4440 KB Output is correct
8 Correct 1 ms 4700 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 0 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 4696 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4548 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4696 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 3 ms 4604 KB Output is correct
28 Correct 2 ms 4444 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 2 ms 4444 KB Output is correct
32 Correct 2 ms 4556 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 44776 KB Output is correct
2 Correct 239 ms 53416 KB Output is correct
3 Correct 252 ms 44628 KB Output is correct
4 Correct 260 ms 46928 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4540 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 0 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4444 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 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 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 0 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 2 ms 4444 KB Output is correct
27 Correct 3 ms 4440 KB Output is correct
28 Correct 2 ms 4504 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 2 ms 4444 KB Output is correct
32 Correct 3 ms 4444 KB Output is correct
33 Correct 34 ms 20272 KB Output is correct
34 Correct 29 ms 20340 KB Output is correct
35 Correct 142 ms 48076 KB Output is correct
36 Correct 124 ms 47952 KB Output is correct
37 Correct 63 ms 19104 KB Output is correct
38 Correct 68 ms 31568 KB Output is correct
39 Correct 22 ms 19024 KB Output is correct
40 Correct 110 ms 44776 KB Output is correct
41 Correct 45 ms 19284 KB Output is correct
42 Correct 53 ms 19020 KB Output is correct
43 Correct 107 ms 45140 KB Output is correct
44 Correct 109 ms 45228 KB Output is correct

Subtask #5
23.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 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 4536 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 0 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 0 ms 4444 KB Output is correct
20 Correct 0 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 2 ms 4444 KB Output is correct
26 Correct 1 ms 4440 KB Output is correct
27 Correct 3 ms 4440 KB Output is correct
28 Correct 2 ms 4444 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct
31 Correct 2 ms 4576 KB Output is correct
32 Correct 3 ms 4444 KB Output is correct
33 Correct 428 ms 44884 KB Output is correct
34 Correct 228 ms 49744 KB Output is correct
35 Correct 259 ms 44876 KB Output is correct
36 Correct 249 ms 47188 KB Output is correct
37 Correct 29 ms 20304 KB Output is correct
38 Correct 30 ms 20324 KB Output is correct
39 Correct 136 ms 48080 KB Output is correct
40 Correct 132 ms 48180 KB Output is correct
41 Correct 57 ms 19280 KB Output is correct
42 Correct 68 ms 31572 KB Output is correct
43 Correct 22 ms 19032 KB Output is correct
44 Correct 112 ms 44856 KB Output is correct
45 Correct 41 ms 19024 KB Output is correct
46 Correct 53 ms 19036 KB Output is correct
47 Correct 109 ms 45140 KB Output is correct
48 Correct 109 ms 45140 KB Output is correct
49 Correct 102 ms 23120 KB Output is correct
50 Correct 91 ms 22872 KB Output is correct
51 Correct 262 ms 49752 KB Output is correct
52 Correct 187 ms 48980 KB Output is correct
53 Correct 425 ms 21892 KB Output is correct
54 Correct 199 ms 34984 KB Output is correct
55 Correct 89 ms 19696 KB Output is correct
56 Correct 193 ms 46396 KB Output is correct
57 Correct 270 ms 20284 KB Output is correct
58 Correct 373 ms 20564 KB Output is correct
59 Correct 111 ms 45140 KB Output is correct