oj.uz

Submission #1018421

# Submission time Handle Problem Language Result Execution time Memory
1018421 2024-07-10T03:24:00 Z huutuan Horses (IOI15_horses) C++14
17 / 100
 698 ms 54240 KB 
#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct SegmentTree{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, 0);
   }
   void build(int k, int l, int r, int a[]){
      if (l==r){
         t[k]=a[l];
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, a);
      build(k<<1|1, mid+1, r, a);
      t[k]=max(t[k<<1], t[k<<1|1]);
   }
   void update(int k, int l, int r, int pos, int val){
      if (l==r){
         t[k]=val;
         return;
      }
      int mid=(l+r)>>1;
      if (pos<=mid) update(k<<1, l, mid, pos, val);
      else update(k<<1|1, mid+1, r, pos, val);
      t[k]=max(t[k<<1], t[k<<1|1]);
   }
   int get(int k, int l, int r, int L, int R){
      if (r<L || R<l) return 0;
      if (L<=l && r<=R) return t[k];
      int mid=(l+r)>>1;
      return max(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
   }
} st;

const int N=5e5+10, mod=1e9+7;

int binpow(int x, int y){
   int t=1;
   while (y){
      if (y&1) t=1ll*t*x%mod;
      x=1ll*x*x%mod;
      y>>=1;
   }
   return t;
}

set<int> pos;
int n, a[N], b[N];
int prod;

int solve(){
   vector<pair<long long, int>> v;
   int p=1;
   for (auto it=pos.rbegin(); it!=pos.rend(); ++it){
      if (a[*it]>=(mod+p-1)/p) break;
      p*=a[*it];
      v.emplace_back(0, *it);
   }
   reverse(v.begin(), v.end());
   int ans=prod;
   int cur=1;
   for (int i=0; i<(int)v.size(); ++i){
      ans=1ll*ans*binpow(a[v[i].second], mod-2)%mod;
      cur*=a[v[i].second];
      v[i].first=1ll*cur*st.get(1, 1, n, v[i].second, i+1==(int)v.size()?n:v[i+1].second-1);
   }
   auto opt=*max_element(v.begin(), v.end());
   return 1ll*ans*(opt.first%mod)%mod;
}

int32_t init(int32_t _N, int32_t X[], int32_t Y[]) {
   n=_N;
   st.init(n);
   prod=1;
   for (int i=1; i<=n; ++i){
      a[i]=X[i-1], b[i]=Y[i-1];
      if (a[i]!=1 || i==1) pos.insert(i);
      prod=1ll*prod*a[i]%mod;
   }
   st.build(1, 1, n, b);
   return solve();
}

int32_t updateX(int32_t i, int32_t val) {
   ++i;
   prod=1ll*prod*binpow(a[i], mod-2)%mod;
   prod=1ll*prod*val%mod;
   a[i]=val;
   pos.erase(i);
   if (a[i]!=1 || i==1) pos.insert(i);
   return solve();
}

int32_t updateY(int32_t i, int32_t val) {
   ++i;
   b[i]=val;
   st.update(1, 1, n, i, val);
   return solve();
}

Compilation message

horses.cpp: In function 'int32_t init(int32_t, int32_t*, int32_t*)':
horses.cpp:90:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
   90 |    return solve();
      |           ~~~~~^~
horses.cpp: In function 'int32_t updateX(int32_t, int32_t)':
horses.cpp:100:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  100 |    return solve();
      |           ~~~~~^~
horses.cpp: In function 'int32_t updateY(int32_t, int32_t)':
horses.cpp:107:16: warning: conversion from 'long long int' to 'int32_t' {aka 'int'} may change value [-Wconversion]
  107 |    return solve();
      |           ~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2496 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Incorrect 0 ms 2396 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 698 ms 54240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2496 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2392 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Incorrect 0 ms 2396 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2392 KB Output is correct
16 Correct 0 ms 2652 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Incorrect 0 ms 2396 KB Output isn't correct
23 Halted 0 ms 0 KB -