oj.uz

Submission #727016

# Submission time Handle Problem Language Result Execution time Memory
727016 2023-04-19T20:08:45 Z Yell0 Horses (IOI15_horses) C++17
100 / 100
 1092 ms 84260 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MOD=1e9+7;
ll modinv(ll a) {
  ll res=1;
  for(ll i=0;(1LL<<i)<=MOD-2;++i) {
    if((MOD-2)&(1LL<<i)) res=res*a%MOD;
    a=a*a%MOD;
  }
  return res;
}

int N;
vector<ll> bit,X,Y;
set<pii> iv;
void upd(int i,int a) {
  for(;i<=N;i+=-i&i) bit[i]=bit[i]*a%MOD;
}
ll qry(int i) {
  ll res=1;
  for(;i>0;i-=-i&i) res=res*bit[i]%MOD;
  return res;
}
struct node{int l,r;ll mx=1;};
vector<node> seg;
void bldmx(int l,int r,int i) {
  seg[i].l=l;
  seg[i].r=r;
  if(l==r) return;
  int mid=(l+r)/2;
  bldmx(l,mid,i*2);
  bldmx(mid+1,r,i*2+1);
  seg[i].mx=max(seg[i*2].mx,seg[i*2+1].mx);
}
void updmx(int p,ll v,int i) {
  if(seg[i].l==p&&p==seg[i].r) {
    seg[i].mx=v;
    return;
  }
  int mid=(seg[i].l+seg[i].r)/2;
  if(p<=mid) updmx(p,v,i*2);
  else updmx(p,v,i*2+1);
  seg[i].mx=max(seg[i*2].mx,seg[i*2+1].mx);
}
ll qrymx(int l,int r,int i) {
  if(seg[i].l==l&&seg[i].r==r) return seg[i].mx;
  int mid=(seg[i].l+seg[i].r)/2;
  if(r<=mid) return qrymx(l,r,i*2);
  else if(l>mid) return qrymx(l,r,i*2+1);
  else return max(qrymx(l,mid,i*2),qrymx(mid+1,r,i*2+1));
}

ll fndmx() {
  ll pfx=1,sfx=1,mpfx=1;
  auto sti=--iv.end();
  for(auto i=sti;i!=--iv.begin();--i) {
    sfx*=X[i->first];
    sti=i;
    if(sfx>=(ll)1e9) break;
  }
  auto mxi=sti;
  for(auto i=sti;i!=iv.end();++i) {
    pfx*=X[i->first];
    if(pfx/mpfx>qrymx(mxi->first,mxi->second,1)/qrymx(i->first,i->second,1)) {
      mxi=i;
      mpfx=pfx;
    }
  }
  return qry(mxi->first)*qrymx(mxi->first,mxi->second,1)%MOD;
}

int init(int n,int x[],int y[]) {
  N=n;
  bit.resize(N+2,1);
  X.resize(N+2,1);
  Y.resize(N+2,1);
  seg.resize(N*4);
  bldmx(1,N,1);
  for(int i=1;i<=N;++i) {
    upd(i,x[i-1]);
    X[i]=x[i-1];
    updmx(i,y[i-1],1);
    Y[i]=y[i-1];
  }
  int st=1,ed=1;
  for(int i=1;i<=N;++i) {
    ed=i;
    if(X[i]==1) {
      if(X[i-1]>1) st=i;
      if(X[i+1]>1||i==N) iv.insert({st,ed});
      continue;
    }
    st=i;
    iv.insert({st,ed});
  }
  return fndmx();
}
int updateX(int i,int a) {
  ++i;
  if(X[i]==1&&a!=1) {
    pii old=*(--iv.upper_bound({i,INT_MAX}));
    if(old.first!=old.second) {
      iv.erase(old);
      if(i==old.first) iv.insert({old.first+1,old.second});
      else if(i==old.second) iv.insert({old.first,old.second-1});
      else { 
        iv.insert({old.first,i-1});
        iv.insert({i+1,old.second});
      }
      iv.insert({i,i});
    }
  }
  if(a==1&&X[i]!=1) {
    pii curr={i,i};
    int st=0,ed=0;
    if(X[i-1]==1&&i!=1) {
      st=(--iv.lower_bound(curr))->first;
      iv.erase(--iv.lower_bound(curr));
    }
    if(X[i+1]==1&&i!=N) {
      ed=(iv.upper_bound(curr))->second;
      iv.erase(iv.upper_bound(curr));
    }
    iv.erase(curr);
    iv.insert({(st?st:i),(ed?ed:i)});
  }
  upd(i,modinv(X[i])*a%MOD);
  X[i]=a;
  return fndmx();
}
int updateY(int i,int a) {
  ++i;
  Y[i]=a;
  updmx(i,a,1);
  return fndmx();
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:99:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   99 |   return fndmx();
      |          ~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:130:23: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  130 |   upd(i,modinv(X[i])*a%MOD);
      |         ~~~~~~~~~~~~~~^~~~
horses.cpp:132:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  132 |   return fndmx();
      |          ~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:138:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  138 |   return fndmx();
      |          ~~~~~^~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 71732 KB Output is correct
2 Correct 352 ms 71644 KB Output is correct
3 Correct 358 ms 71720 KB Output is correct
4 Correct 348 ms 71684 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 2 ms 444 KB Output is correct
26 Correct 2 ms 440 KB Output is correct
27 Correct 4 ms 312 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 2 ms 436 KB Output is correct
31 Correct 3 ms 308 KB Output is correct
32 Correct 5 ms 340 KB Output is correct
33 Correct 137 ms 51508 KB Output is correct
34 Correct 140 ms 51444 KB Output is correct
35 Correct 282 ms 81792 KB Output is correct
36 Correct 260 ms 81584 KB Output is correct
37 Correct 205 ms 49664 KB Output is correct
38 Correct 241 ms 73832 KB Output is correct
39 Correct 124 ms 49264 KB Output is correct
40 Correct 248 ms 76632 KB Output is correct
41 Correct 152 ms 49312 KB Output is correct
42 Correct 197 ms 49480 KB Output is correct
43 Correct 247 ms 77132 KB Output is correct
44 Correct 232 ms 77044 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 436 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 5 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 3 ms 340 KB Output is correct
30 Correct 3 ms 468 KB Output is correct
31 Correct 4 ms 308 KB Output is correct
32 Correct 6 ms 340 KB Output is correct
33 Correct 569 ms 75548 KB Output is correct
34 Correct 353 ms 84260 KB Output is correct
35 Correct 364 ms 75532 KB Output is correct
36 Correct 385 ms 79332 KB Output is correct
37 Correct 143 ms 51448 KB Output is correct
38 Correct 132 ms 51448 KB Output is correct
39 Correct 291 ms 81632 KB Output is correct
40 Correct 264 ms 81532 KB Output is correct
41 Correct 235 ms 49652 KB Output is correct
42 Correct 262 ms 73932 KB Output is correct
43 Correct 140 ms 49340 KB Output is correct
44 Correct 271 ms 76664 KB Output is correct
45 Correct 164 ms 49400 KB Output is correct
46 Correct 227 ms 49352 KB Output is correct
47 Correct 240 ms 77108 KB Output is correct
48 Correct 247 ms 77080 KB Output is correct
49 Correct 281 ms 55460 KB Output is correct
50 Correct 265 ms 55504 KB Output is correct
51 Correct 443 ms 83544 KB Output is correct
52 Correct 378 ms 82988 KB Output is correct
53 Correct 907 ms 53856 KB Output is correct
54 Correct 494 ms 75628 KB Output is correct
55 Correct 266 ms 50348 KB Output is correct
56 Correct 415 ms 78532 KB Output is correct
57 Correct 528 ms 51132 KB Output is correct
58 Correct 1092 ms 51464 KB Output is correct
59 Correct 276 ms 77088 KB Output is correct