oj.uz

Submission #225559

# Submission time Handle Problem Language Result Execution time Memory
225559 2020-04-20T20:43:35 Z nickmet2004 Horses (IOI15_horses) C++11
100 / 100
 792 ms 49400 KB 
#include "horses.h"
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 500005;
const ll mod = 1e9 + 7;

int n;
set<int> changes;
vector<int> x , y;
ll xmult = 1;
int T[1 << 20];

ll Pow(ll a, ll p)
{
    if (p == 0) return 1;
    if (p & 1) return (a * Pow(a, p - 1)) % mod;
    return Pow((a * a) % mod, p / 2);
}
inline ll Inv(ll a) {return Pow(a % mod, mod - 2);}

void upd(int idx , int v , int l = 0 , int r = n - 1 , int pos = 1){
    if(l == r){
        T[pos] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if(idx <= mid) upd(idx , v , l , mid , pos * 2);
    else upd(idx , v , mid + 1 , r , pos * 2 + 1);
    T[pos] = max(T[pos * 2] , T[pos * 2 + 1]);
}
int get(int L , int R , int l = 0 , int r=  n -1 , int pos = 1){
    if(r < L || R < l) return -2e9;
    if(L <= l && r <= R) return T[pos];
    int mid = (l + r) >> 1;
    return max(get(L , R , l , mid , pos * 2) , get(L , R , mid + 1 , r , pos *2 +1));
}
struct div{
    ll a , b;
    bool operator<(const div&Q) const {
        return a * Q.b < Q.a * b;
    }
}mx;

int solve(){
    mx.a = 0; mx.b = 1;
    ll curxmult = 1;
    for(auto it = changes.rbegin(); it != changes.rend() && curxmult < 1000000000; ++it){
        int i = *it;
        int j = (it == changes.rbegin() ? n : *prev(it));
        mx = max(mx , {get(i, j - 1) , curxmult});
        curxmult *= x[i];
    }
    ll res = (mx.a * Inv(mx.b)) % mod;
    return res = (res * xmult) % mod;
}
int init(int N , int X[] , int Y[]){
    n = N;
    x.assign(X , X + N);
    y.assign(Y , Y + N);
    for(int i = 0; i < n; ++i){
        upd(i , y[i]);
    }
    changes.insert(0);
    for(int i = 0; i < n; ++i){
        if(x[i] > 1){
            changes.insert(i);
            xmult = (xmult * x[i]) % mod;
        }
    }
    return solve();
}
int updateX(int pos , int val){
    if(pos && x[pos] > 1 && val == 1) changes.erase(pos);
    if(pos && x[pos] == 1 && val > 1) changes.insert(pos);
    xmult = (xmult * Inv(x[pos])) % mod;
    xmult = (xmult * (x[pos] = val))% mod;
    return solve();
}
int updateY(int pos , int val){
    upd(pos , (y[pos] = val));
    return solve();
}
///int main (){}

Compilation message

horses.cpp: In function 'int solve()':
horses.cpp:57:16: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return res = (res * xmult) % mod;
            ~~~~^~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:59:35: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N , int X[] , int Y[]){
                                   ^
horses.cpp:7:11: note: shadowed declaration is here
 const int N = 500005;
           ^

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 36872 KB Output is correct
2 Correct 330 ms 36704 KB Output is correct
3 Correct 348 ms 36728 KB Output is correct
4 Correct 384 ms 36840 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 256 KB Output is correct
12 Correct 4 ms 256 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 256 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 6 ms 512 KB Output is correct
27 Correct 8 ms 384 KB Output is correct
28 Correct 6 ms 512 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 6 ms 384 KB Output is correct
31 Correct 7 ms 384 KB Output is correct
32 Correct 9 ms 384 KB Output is correct
33 Correct 109 ms 16504 KB Output is correct
34 Correct 107 ms 16376 KB Output is correct
35 Correct 260 ms 46764 KB Output is correct
36 Correct 252 ms 46692 KB Output is correct
37 Correct 171 ms 14584 KB Output is correct
38 Correct 166 ms 27384 KB Output is correct
39 Correct 104 ms 14328 KB Output is correct
40 Correct 242 ms 41848 KB Output is correct
41 Correct 130 ms 14456 KB Output is correct
42 Correct 143 ms 14456 KB Output is correct
43 Correct 229 ms 42208 KB Output is correct
44 Correct 265 ms 42148 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 256 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Correct 4 ms 256 KB Output is correct
21 Correct 5 ms 256 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 5 ms 512 KB Output is correct
27 Correct 8 ms 384 KB Output is correct
28 Correct 6 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 6 ms 512 KB Output is correct
31 Correct 7 ms 384 KB Output is correct
32 Correct 8 ms 384 KB Output is correct
33 Correct 792 ms 40804 KB Output is correct
34 Correct 339 ms 49400 KB Output is correct
35 Correct 417 ms 40696 KB Output is correct
36 Correct 406 ms 44536 KB Output is correct
37 Correct 111 ms 16504 KB Output is correct
38 Correct 105 ms 16504 KB Output is correct
39 Correct 259 ms 46892 KB Output is correct
40 Correct 248 ms 46712 KB Output is correct
41 Correct 165 ms 14584 KB Output is correct
42 Correct 174 ms 27356 KB Output is correct
43 Correct 103 ms 14328 KB Output is correct
44 Correct 239 ms 41720 KB Output is correct
45 Correct 131 ms 14456 KB Output is correct
46 Correct 150 ms 14456 KB Output is correct
47 Correct 234 ms 42104 KB Output is correct
48 Correct 219 ms 42108 KB Output is correct
49 Correct 221 ms 19456 KB Output is correct
50 Correct 216 ms 19448 KB Output is correct
51 Correct 434 ms 48792 KB Output is correct
52 Correct 333 ms 48120 KB Output is correct
53 Correct 776 ms 18040 KB Output is correct
54 Correct 380 ms 31224 KB Output is correct
55 Correct 220 ms 15480 KB Output is correct
56 Correct 348 ms 43640 KB Output is correct
57 Correct 499 ms 16120 KB Output is correct
58 Correct 701 ms 16760 KB Output is correct
59 Correct 229 ms 42232 KB Output is correct