oj.uz

Submission #262400

# Submission time Handle Problem Language Result Execution time Memory
262400 2020-08-12T21:03:39 Z uacoder123 Horses (IOI15_horses) C++14
100 / 100
 987 ms 104056 KB 
#include <bits/stdc++.h>
    #include "horses.h"
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;

pair<lli,int> segt[2000001],segt1[2000001];;
lli lazy[2000001],arr1[500001],arr2[500001];
lli n,mod=1000000007;
lli p(lli a)
{
  lli b=0,ans=1;
  while((1LL<<b)<=mod-2)
  {
    if(bit(mod-2,b))
      ans=(ans*a)%mod;
    a=(a*a)%mod;
    b++;
  }
  return ans;
}

void up(lli node,lli l,lli r,lli s,lli e,lli v)
{ 
  if(lazy[node]!=1)
  {
    segt[node].F=(segt[node].F*lazy[node])%mod;
    if(l!=r)
    {
      lazy[2*node+1]=(lazy[2*node+1]*lazy[node])%mod;
      lazy[2*node+2]=(lazy[2*node+2]*lazy[node])%mod;
    }
    lazy[node]=1;
  }
  if(l>e||r<s)
    return;
  if(l>=s&&r<=e)
  {
    if(l==r)
      segt[node].S=l;
    segt[node].F=(segt[node].F*v)%mod;
    if(l!=r)
    {
      lazy[2*node+1]=(lazy[2*node+1]*v)%mod;
      lazy[2*node+2]=(lazy[2*node+2]*v)%mod;
    }
    return;
  }
  lli m=(l+r)/2;
  up(2*node+1,l,m,s,e,v);
  up(2*node+2,m+1,r,s,e,v);
}
void up1(int node,int l,int r,int in)
{
  if(lazy[node]!=1)
  {
    segt[node].F=(segt[node].F*lazy[node])%mod;
    if(l!=r)
    {
      lazy[2*node+1]=(lazy[2*node+1]*lazy[node])%mod;
      lazy[2*node+2]=(lazy[2*node+2]*lazy[node])%mod;
    }
    lazy[node]=1;
  }
  if(l==r)
    return;
  int m=(l+r)/2;
  if(in<=m)
    up1(2*node+1,l,m,in);
  else
    up1(2*node+2,m+1,r,in);
  up(2*node+1,l,m,l,m,1);
  up(2*node+2,m+1,r,m+1,r,1);
  if(min(mod,min(mod,min(segt1[2*node+1].S*segt1[2*node+2].F,mod)*arr1[segt[2*node+2].S])*arr2[segt[2*node+2].S])<arr2[segt[2*node+1].S])
  {
    segt1[node].F=segt1[2*node+1].F;
    segt1[node].S=min(mod,min(mod,min(mod,segt1[2*node+1].S*segt1[2*node+2].F)*segt1[2*node+2].S)*arr1[segt[2*node+2].S]);
    segt[node]=segt[2*node+1];
  }
  else
  {
    segt1[node].S=segt1[2*node+2].S;
    segt1[node].F=min(mod,min(mod,min(mod,segt1[2*node+1].F*segt1[2*node+1].S)*segt1[2*node+2].F)*arr1[segt[2*node+1].S]);
    segt[node]=segt[2*node+2];
  }
}
int init(int N, int X[], int Y[]) 
{
  for(lli i=0;i<=2000001;++i)
  {
    segt[i].F=1;
    segt1[i].F=1;
    segt1[i].S=1;
    lazy[i]=1;
  }
  n=N;
  lli cur=(1);
  for(int i=0;i<n;++i)
  {
    arr1[i]=X[i];
    arr2[i]=Y[i];
  }
  for(lli i=0;i<n;++i)
  {
    cur=(cur*X[i])%mod;
    up(0,0,n-1,i,i,(cur*Y[i])%mod);
    up1(0,0,n-1,i);
  }
  return segt[0].F;
}

int updateX(int pos, int val) 
{
  lli v=p(arr1[pos]);
  v=(v*val)%mod;
  arr1[pos]=val;
  up(0,0,n-1,pos,n-1,v);
  up1(0,0,n-1,pos);
  return segt[0].F;
}
int updateY(int pos, int val) 
{
  lli v=p(arr2[pos]);
  v=(v*val)%mod;
  arr2[pos]=val;
  up(0,0,n-1,pos,pos,v);
  up1(0,0,n-1,pos);
  return segt[0].F;
}

Compilation message

horses.cpp: In function 'lli p(lli)':
horses.cpp:27:15: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   27 |     if(bit(mod-2,b))
      |            ~~~^~
horses.cpp:12:19: note: in definition of macro 'bit'
   12 | #define bit(x,b) (x&(1LL<<b))
      |                   ^
horses.cpp: In function 'void up(lli, lli, lli, lli, lli, lli)':
horses.cpp:52:20: warning: conversion from 'lli' {aka 'long long int'} to 'int' may change value [-Wconversion]
   52 |       segt[node].S=l;
      |                    ^
horses.cpp: In function 'void up1(int, int, int, int)':
horses.cpp:89:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |     segt1[node].S=min(mod,min(mod,min(mod,segt1[2*node+1].S*segt1[2*node+2].F)*segt1[2*node+2].S)*arr1[segt[2*node+2].S]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:119:14: warning: conversion from 'lli' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |     up1(0,0,n-1,i);
      |             ~^~
horses.cpp:119:17: warning: conversion from 'lli' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |     up1(0,0,n-1,i);
      |                 ^
horses.cpp:4:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    4 | #define F first
      |           ^
horses.cpp:121:18: note: in expansion of macro 'F'
  121 |   return segt[0].F;
      |                  ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:130:12: warning: conversion from 'lli' {aka 'long long int'} to 'int' may change value [-Wconversion]
  130 |   up1(0,0,n-1,pos);
      |           ~^~
horses.cpp:4:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    4 | #define F first
      |           ^
horses.cpp:131:18: note: in expansion of macro 'F'
  131 |   return segt[0].F;
      |                  ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:139:12: warning: conversion from 'lli' {aka 'long long int'} to 'int' may change value [-Wconversion]
  139 |   up1(0,0,n-1,pos);
      |           ~^~
horses.cpp:4:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
    4 | #define F first
      |           ^
horses.cpp:140:18: note: in expansion of macro 'F'
  140 |   return segt[0].F;
      |                  ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:103:14: warning: iteration 2000001 invokes undefined behavior [-Waggressive-loop-optimizations]
  103 |     segt[i].F=1;
      |     ~~~~~~~~~^~
horses.cpp:101:16: note: within this loop
  101 |   for(lli i=0;i<=2000001;++i)
      |               ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 78584 KB Output is correct
2 Correct 43 ms 78584 KB Output is correct
3 Correct 43 ms 78584 KB Output is correct
4 Correct 43 ms 78584 KB Output is correct
5 Correct 44 ms 78584 KB Output is correct
6 Correct 46 ms 78584 KB Output is correct
7 Correct 44 ms 78592 KB Output is correct
8 Correct 43 ms 78660 KB Output is correct
9 Correct 43 ms 78584 KB Output is correct
10 Correct 45 ms 78592 KB Output is correct
11 Correct 44 ms 78584 KB Output is correct
12 Correct 44 ms 78584 KB Output is correct
13 Correct 44 ms 78584 KB Output is correct
14 Correct 44 ms 78712 KB Output is correct
15 Correct 43 ms 78584 KB Output is correct
16 Correct 43 ms 78584 KB Output is correct
17 Correct 43 ms 78584 KB Output is correct
18 Correct 43 ms 78584 KB Output is correct
19 Correct 43 ms 78584 KB Output is correct
20 Correct 44 ms 78708 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 78584 KB Output is correct
2 Correct 48 ms 78584 KB Output is correct
3 Correct 47 ms 78588 KB Output is correct
4 Correct 46 ms 78584 KB Output is correct
5 Correct 46 ms 78584 KB Output is correct
6 Correct 43 ms 78584 KB Output is correct
7 Correct 44 ms 78584 KB Output is correct
8 Correct 54 ms 78584 KB Output is correct
9 Correct 54 ms 78584 KB Output is correct
10 Correct 43 ms 78584 KB Output is correct
11 Correct 43 ms 78584 KB Output is correct
12 Correct 54 ms 78584 KB Output is correct
13 Correct 44 ms 78584 KB Output is correct
14 Correct 44 ms 78584 KB Output is correct
15 Correct 45 ms 78588 KB Output is correct
16 Correct 43 ms 78584 KB Output is correct
17 Correct 43 ms 78584 KB Output is correct
18 Correct 52 ms 78584 KB Output is correct
19 Correct 44 ms 78584 KB Output is correct
20 Correct 43 ms 78584 KB Output is correct
21 Correct 43 ms 78584 KB Output is correct
22 Correct 46 ms 78712 KB Output is correct
23 Correct 45 ms 78672 KB Output is correct
24 Correct 45 ms 78584 KB Output is correct
25 Correct 51 ms 78712 KB Output is correct
26 Correct 46 ms 78712 KB Output is correct
27 Correct 47 ms 78712 KB Output is correct
28 Correct 45 ms 78584 KB Output is correct
29 Correct 45 ms 78584 KB Output is correct
30 Correct 45 ms 78712 KB Output is correct
31 Correct 44 ms 78584 KB Output is correct
32 Correct 44 ms 78720 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 91988 KB Output is correct
2 Correct 987 ms 103980 KB Output is correct
3 Correct 916 ms 95224 KB Output is correct
4 Correct 955 ms 99064 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 78584 KB Output is correct
2 Correct 42 ms 78584 KB Output is correct
3 Correct 42 ms 78584 KB Output is correct
4 Correct 42 ms 78712 KB Output is correct
5 Correct 42 ms 78584 KB Output is correct
6 Correct 42 ms 78584 KB Output is correct
7 Correct 42 ms 78584 KB Output is correct
8 Correct 42 ms 78712 KB Output is correct
9 Correct 42 ms 78584 KB Output is correct
10 Correct 43 ms 78584 KB Output is correct
11 Correct 42 ms 78584 KB Output is correct
12 Correct 42 ms 78588 KB Output is correct
13 Correct 42 ms 78584 KB Output is correct
14 Correct 43 ms 78584 KB Output is correct
15 Correct 44 ms 78592 KB Output is correct
16 Correct 42 ms 78584 KB Output is correct
17 Correct 43 ms 78652 KB Output is correct
18 Correct 42 ms 78584 KB Output is correct
19 Correct 42 ms 78584 KB Output is correct
20 Correct 43 ms 78584 KB Output is correct
21 Correct 47 ms 78584 KB Output is correct
22 Correct 43 ms 78584 KB Output is correct
23 Correct 44 ms 78712 KB Output is correct
24 Correct 44 ms 78712 KB Output is correct
25 Correct 44 ms 78712 KB Output is correct
26 Correct 47 ms 78712 KB Output is correct
27 Correct 44 ms 78712 KB Output is correct
28 Correct 44 ms 78712 KB Output is correct
29 Correct 48 ms 78584 KB Output is correct
30 Correct 44 ms 78612 KB Output is correct
31 Correct 45 ms 78720 KB Output is correct
32 Correct 46 ms 78584 KB Output is correct
33 Correct 610 ms 90668 KB Output is correct
34 Correct 624 ms 90744 KB Output is correct
35 Correct 637 ms 101288 KB Output is correct
36 Correct 606 ms 101240 KB Output is correct
37 Correct 578 ms 92536 KB Output is correct
38 Correct 578 ms 93424 KB Output is correct
39 Correct 571 ms 92468 KB Output is correct
40 Correct 601 ms 96472 KB Output is correct
41 Correct 579 ms 92536 KB Output is correct
42 Correct 565 ms 92540 KB Output is correct
43 Correct 574 ms 96776 KB Output is correct
44 Correct 574 ms 96780 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 78584 KB Output is correct
2 Correct 41 ms 78584 KB Output is correct
3 Correct 46 ms 78588 KB Output is correct
4 Correct 43 ms 78584 KB Output is correct
5 Correct 41 ms 78584 KB Output is correct
6 Correct 41 ms 78592 KB Output is correct
7 Correct 41 ms 78584 KB Output is correct
8 Correct 42 ms 78584 KB Output is correct
9 Correct 42 ms 78584 KB Output is correct
10 Correct 41 ms 78648 KB Output is correct
11 Correct 41 ms 78592 KB Output is correct
12 Correct 41 ms 78584 KB Output is correct
13 Correct 41 ms 78584 KB Output is correct
14 Correct 43 ms 78584 KB Output is correct
15 Correct 42 ms 78584 KB Output is correct
16 Correct 42 ms 78584 KB Output is correct
17 Correct 43 ms 78584 KB Output is correct
18 Correct 43 ms 78584 KB Output is correct
19 Correct 43 ms 78584 KB Output is correct
20 Correct 41 ms 78584 KB Output is correct
21 Correct 41 ms 78584 KB Output is correct
22 Correct 41 ms 78584 KB Output is correct
23 Correct 43 ms 78712 KB Output is correct
24 Correct 43 ms 78712 KB Output is correct
25 Correct 43 ms 78712 KB Output is correct
26 Correct 42 ms 78712 KB Output is correct
27 Correct 44 ms 78712 KB Output is correct
28 Correct 43 ms 78712 KB Output is correct
29 Correct 44 ms 78584 KB Output is correct
30 Correct 43 ms 78712 KB Output is correct
31 Correct 43 ms 78712 KB Output is correct
32 Correct 42 ms 78584 KB Output is correct
33 Correct 709 ms 91808 KB Output is correct
34 Correct 961 ms 104056 KB Output is correct
35 Correct 908 ms 95180 KB Output is correct
36 Correct 966 ms 98992 KB Output is correct
37 Correct 602 ms 94456 KB Output is correct
38 Correct 621 ms 94328 KB Output is correct
39 Correct 618 ms 101368 KB Output is correct
40 Correct 621 ms 101368 KB Output is correct
41 Correct 584 ms 92552 KB Output is correct
42 Correct 580 ms 93432 KB Output is correct
43 Correct 572 ms 92408 KB Output is correct
44 Correct 599 ms 96376 KB Output is correct
45 Correct 569 ms 92536 KB Output is correct
46 Correct 563 ms 92540 KB Output is correct
47 Correct 575 ms 97016 KB Output is correct
48 Correct 577 ms 96888 KB Output is correct
49 Correct 907 ms 96508 KB Output is correct
50 Correct 925 ms 96416 KB Output is correct
51 Correct 745 ms 103216 KB Output is correct
52 Correct 767 ms 102776 KB Output is correct
53 Correct 877 ms 94968 KB Output is correct
54 Correct 735 ms 95252 KB Output is correct
55 Correct 731 ms 93688 KB Output is correct
56 Correct 801 ms 98168 KB Output is correct
57 Correct 702 ms 94200 KB Output is correct
58 Correct 695 ms 94584 KB Output is correct
59 Correct 570 ms 96888 KB Output is correct