oj.uz

Submission #387431

# Submission time Handle Problem Language Result Execution time Memory
387431 2021-04-08T11:32:18 Z mehrdad_sohrabi Horses (IOI15_horses) C++14
100 / 100
 638 ms 45072 KB 
/// Black lives matter
#include <bits/stdc++.h>
#include "horses.h"
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=5e5+10;
ll seg[N*4];
set <int> s;
ll x[N],y[N];
ll n;
ll mod=1e9+7;
ll ans=1;
ll power(ll n,ll k){
    if (k==0) return 1;
    if (k%2==1){
        ll x=power(n,k/2);
        return x*x%mod*n%mod;
    }
    ll x=power(n,k/2);
    return x*x%mod;
}
void upd(ll nod,ll l,ll r,ll id,ll val){
    if (r-l==1){
        seg[nod]=val;
        return ;
    }
    ll mid=(r+l)/2;
    if (mid>id) upd(nod*2,l,mid,id,val);
    else upd(nod*2+1,mid,r,id,val);
    seg[nod]=max(seg[nod*2],seg[nod*2+1]);
}
ll get(ll nod,ll l,ll r,ll L,ll R){
    if (l>=R || L>=r) return 0;
    if (l>=L && r<=R) return seg[nod];
    ll mid=(r+l)/2;
    return max( get(nod*2,l,mid,L,R), get(nod*2+1,mid,r,L,R));
}
ll solve(){
    ll jav=ans;
    ll cnt=1;
    pii best={1,1};
    auto t=s.end();
    ll p1=0;
    for (int i=0;i<min((ll)s.size(),(ll)30);i++){
        t--;
        ll z=get(1,0,n,*t,n);
        if (z*best.S>cnt*best.F){
            best={z,cnt};
            jav=ans*power(cnt,mod-2)%mod*z%mod;
        }
        cnt*=x[*t];
        if (cnt>(ll)1e9){
            p1=1;
            break;
        }
    }
    if (p1==0){
        ll z=get(1,0,n,0,n);
       // cout << z << endl;
        if (z*best.S>cnt*best.F) jav=z;
    }
    return jav;
}
int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
    n=N;
    for (int i=0;i<n;i++) {
        x[i]=X[i];
        y[i]=Y[i];
        upd(1,0,n,i,y[i]);
        if (x[i]>1) s.insert(i);
    //    cout << x[i] << endl;
        ans*=x[i];
        ans%=mod;
    }
   // cout << ans << " ans " << endl;
	return solve();
}
int32_t updateX(int32_t pos, int32_t val) {
    ans=ans*power(x[pos],mod-2)%mod;
    ans*=val;
    ans%=mod;
    x[pos]=val;
   // cout << ans << endl;
    if (x[pos]==1) s.erase(pos);
    else s.insert(pos);
	return solve();
}

int32_t updateY(int32_t pos, int32_t val) {
    y[pos]=val;
    upd(1,0,n,pos,val);
	return solve();
}
/*
int32_t X[N],Y[N];
int32_t main(){
    ll n;
    cin >> n;
    for (int i=0;i<n;i++){
        cin >> X[i];
    }
    for (int i=0;i<n;i++){
        cin >> Y[i];
    }
    cout << init(n,X,Y) << endl;;
   // cout << solve() << " solve " << endl;
    ll q;
    cin >> q;
    while(q--){
        ll ty;
        cin >> ty;
        ll pos,val;
        cin >> pos >> val;
        if (ty==1){
            cout << updateX(pos,val) << endl;
        }
        else cout << updateY(pos,val) << endl;;
    }
}
*/
/*


*/

Compilation message

horses.cpp: In function 'll power(ll, ll)':
horses.cpp:25:19: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   25 | ll power(ll n,ll k){
      |                   ^
horses.cpp:22:4: note: shadowed declaration is here
   22 | ll n;
      |    ^
horses.cpp:28:12: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   28 |         ll x=power(n,k/2);
      |            ^
horses.cpp:21:4: note: shadowed declaration is here
   21 | ll x[N],y[N];
      |    ^
horses.cpp:31:8: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   31 |     ll x=power(n,k/2);
      |        ^
horses.cpp:21:4: note: shadowed declaration is here
   21 | ll x[N],y[N];
      |    ^
horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:76:49: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   76 | int32_t init(int32_t N, int32_t X[], int32_t Y[]) {
      |                                                 ^
horses.cpp:18:11: note: shadowed declaration is here
   18 | const int N=5e5+10;
      |           ^
horses.cpp:88:14: warning: conversion from 'll' {aka 'long long int'} to 'int32_t' {aka 'int'} may change value [-Wconversion]
   88 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:98:14: warning: conversion from 'll' {aka 'long long int'} to 'int32_t' {aka 'int'} may change value [-Wconversion]
   98 |  return solve();
      |         ~~~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:104:14: warning: conversion from 'll' {aka 'long long int'} to 'int32_t' {aka 'int'} may change value [-Wconversion]
  104 |  return solve();
      |         ~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 638 ms 45072 KB Output is correct
2 Correct 415 ms 44900 KB Output is correct
3 Correct 363 ms 44744 KB Output is correct
4 Correct 476 ms 44780 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 3 ms 492 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 3 ms 364 KB Output is correct
28 Correct 3 ms 492 KB Output is correct
29 Correct 2 ms 364 KB Output is correct
30 Correct 3 ms 492 KB Output is correct
31 Correct 2 ms 364 KB Output is correct
32 Correct 3 ms 364 KB Output is correct
33 Correct 98 ms 20480 KB Output is correct
34 Correct 98 ms 20460 KB Output is correct
35 Correct 258 ms 44000 KB Output is correct
36 Correct 236 ms 43884 KB Output is correct
37 Correct 117 ms 20460 KB Output is correct
38 Correct 168 ms 32364 KB Output is correct
39 Correct 85 ms 20332 KB Output is correct
40 Correct 222 ms 43884 KB Output is correct
41 Correct 105 ms 20332 KB Output is correct
42 Correct 123 ms 20460 KB Output is correct
43 Correct 223 ms 43756 KB Output is correct
44 Correct 211 ms 43756 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 3 ms 492 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 3 ms 364 KB Output is correct
28 Correct 3 ms 508 KB Output is correct
29 Correct 3 ms 364 KB Output is correct
30 Correct 3 ms 624 KB Output is correct
31 Correct 3 ms 364 KB Output is correct
32 Correct 3 ms 364 KB Output is correct
33 Correct 632 ms 44780 KB Output is correct
34 Correct 465 ms 44816 KB Output is correct
35 Correct 368 ms 44780 KB Output is correct
36 Correct 479 ms 44780 KB Output is correct
37 Correct 97 ms 20460 KB Output is correct
38 Correct 98 ms 20460 KB Output is correct
39 Correct 276 ms 43884 KB Output is correct
40 Correct 243 ms 43884 KB Output is correct
41 Correct 117 ms 20460 KB Output is correct
42 Correct 159 ms 32364 KB Output is correct
43 Correct 84 ms 20332 KB Output is correct
44 Correct 222 ms 43884 KB Output is correct
45 Correct 105 ms 20460 KB Output is correct
46 Correct 119 ms 20332 KB Output is correct
47 Correct 216 ms 43884 KB Output is correct
48 Correct 212 ms 43756 KB Output is correct
49 Correct 222 ms 22380 KB Output is correct
50 Correct 222 ms 22508 KB Output is correct
51 Correct 421 ms 44908 KB Output is correct
52 Correct 343 ms 44748 KB Output is correct
53 Correct 530 ms 22364 KB Output is correct
54 Correct 351 ms 35308 KB Output is correct
55 Correct 161 ms 20588 KB Output is correct
56 Correct 319 ms 44780 KB Output is correct
57 Correct 345 ms 21228 KB Output is correct
58 Correct 503 ms 21484 KB Output is correct
59 Correct 217 ms 43884 KB Output is correct