oj.uz

Submission #66963

# Submission time Handle Problem Language Result Execution time Memory
66963 2018-08-12T21:53:50 Z MKopchev Horses (IOI15_horses) C++14
100 / 100
 1006 ms 252472 KB 
#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
const int nmax=5e5+42,mod=1e9+7,inf=1e9+42;
int n,x[nmax],y[nmax];
set<int> non_zero;
long long tree_x[4*nmax],tree_y[4*nmax];
void build_x(int node,int l,int r)
{
    if(l==r)
    {
    tree_x[node]=x[l];
    return;
    }
    int av=(l+r)/2;
    build_x(node*2,l,av);
    build_x(node*2+1,av+1,r);
    tree_x[node]=(tree_x[node*2]*tree_x[node*2+1])%mod;
}
void update_x(int node,int l,int r,int pos,int val)
{
    if(l==r)
    {

    tree_x[node]=val;
    return;
    }
    int av=(l+r)/2;
    if(pos<=av)update_x(node*2,l,av,pos,val);
    else update_x(node*2+1,av+1,r,pos,val);
    tree_x[node]=(tree_x[node*2]*tree_x[node*2+1])%mod;
}
int query_x(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree_x[node];
    int av=(l+r)/2;
    long long ans=1;
    if(lq<=av)ans=ans*query_x(node*2,l,av,lq,min(av,rq))%mod;
    if(av<rq)ans=ans*query_x(node*2+1,av+1,r,max(av+1,lq),rq)%mod;
    return ans;
}

void build_y(int node,int l,int r)
{
    if(l==r)
    {
    tree_y[node]=y[l];
    return;
    }
    int av=(l+r)/2;
    build_y(node*2,l,av);
    build_y(node*2+1,av+1,r);
    tree_y[node]=max(tree_y[node*2],tree_y[node*2+1]);
}
void update_y(int node,int l,int r,int pos,int val)
{
    assert(l<=pos&&pos<=r);
    if(l==r)
    {
    tree_y[node]=val;
    return;
    }
    int av=(l+r)/2;
    if(pos<=av)update_y(node*2,l,av,pos,val);
    else update_y(node*2+1,av+1,r,pos,val);
    tree_y[node]=max(tree_y[node*2],tree_y[node*2+1]);
}
int query_y(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree_y[node];
    int av=(l+r)/2;
    int ans=0;
    if(lq<=av)ans=max(ans,query_y(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ans=max(ans,query_y(node*2+1,av+1,r,max(av+1,lq),rq));
    return ans;
}


bool bigger(long long a,long long b,long long c)
{
    return a>=(c+b-1)/b;
}
int active[nmax],ind=0;
pair<int,int> slow()
{
    double sum=0,maxi=0,now;
    int ind=0;
    for(int i=0;i<n;i++)
    {
        sum=sum+log10(1.0*x[i]);
        now=sum+log10(1.0*y[i]);
        if(now>maxi+1.0/1e9)
        {
            maxi=now;
            ind=i;
        }
    }
    long long res=y[ind];
    for(int i=0;i<=ind;i++)
    {
        res=res*x[i]%mod;
    }
    return {res,ind};
}
void test(long long a,long long b,long long &c,long long &d)
{
    double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
    if(p>q+1.0/1e9)
    {
        c=a;
        d=b;
    }
}
int query()
{
    if(non_zero.size()==0)return query_y(1,0,n-1,0,n-1);
    long long prod=1,maxi=1;
    int last=n,pos=-1;
    ind=0;
    for(auto k:non_zero)
    {
        pos=-k;
        active[++ind]=pos;
        prod=prod*x[pos];
        if(prod>inf)break;
    }
    reverse(active+1,active+ind+1);
    //cout<<"active: ";for(int i=1;i<=ind;i++)cout<<active[i]<<" ";cout<<endl;
    prod=1;
    long long p1,b1=1,b2=1;
    for(int i=1;i<ind;i++)
    {
        prod=prod*x[active[i]];
        //cout<<"q "<<query_y(1,0,n-1,active[i],active[i+1]-1)<<endl;
        p1=query_y(1,0,n-1,active[i],active[i+1]-1);
        test(prod,p1,b1,b2);
    }

    if(ind==non_zero.size())
    {
        if(active[1]!=0)maxi=max(maxi,1LL*query_y(1,0,n-1,0,active[1]-1));
    }

    test(maxi,1,b1,b2);

    //cout<<maxi<<endl;

    long long mult=1;
    if(ind!=non_zero.size())mult=query_x(1,0,n-1,0,active[1]-1);

    long long a=prod*x[active[ind]];
    long long b=query_y(1,0,n-1,active[ind],n-1);

    test(a,b,b1,b2);
    long long ret=mult%mod*(b1%mod)%mod*(b2%mod)%mod;
    /*
    if(n<=1000)
    {
        if(ret!=slow().first)
        {
            cout<<a<<" "<<b<<" "<<maxi<<" "<<mult<<endl;
            cout<<"active: ";for(int i=1;i<=ind;i++)cout<<active[i]<<" ";cout<<endl;
            cout<<ret<<endl;
            for(int i=0;i<n;i++)cout<<x[i]<<" ";cout<<endl;
            cout<<endl;
            for(int i=0;i<n;i++)cout<<y[i]<<" ";cout<<endl;
            cout<<slow().first<<" "<<slow().second<<" "<<x[slow().second]<<" "<<y[slow().second]<<endl;
            system("pause");
            if(bigger(a,b,maxi))
            {
            assert(slow().second>=active[1]);
            while(1);
            }
            else assert(0==1);
        }

    }
    */
    return ret;
}

int init(int N,int X[],int Y[])
{
    n=N;
    for(int i=0;i<N;i++)x[i]=X[i],y[i]=Y[i];
    for(int i=0;i<N;i++)
        if(x[i]!=1)
        {
        non_zero.insert(-i);
        }
    build_x(1,0,n-1);
    build_y(1,0,n-1);
    return query();
}
int updateX(int pos,int val)
{
    if(x[pos]!=1)non_zero.erase(-pos);
    x[pos]=val;
    if(x[pos]!=1)non_zero.insert(-pos);
    update_x(1,0,n-1,pos,val);
    return query();
}
int updateY(int pos,int val)
{
    y[pos]=val;
    update_y(1,0,n-1,pos,val);
    return query();
}

Compilation message

horses.cpp: In function 'int query_x(int, int, int, int, int)':
horses.cpp:35:39: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     if(l==lq&&r==rq)return tree_x[node];
                            ~~~~~~~~~~~^
horses.cpp:40:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ans;
            ^~~
horses.cpp: In function 'int query_y(int, int, int, int, int)':
horses.cpp:70:39: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     if(l==lq&&r==rq)return tree_y[node];
                            ~~~~~~~~~~~^
horses.cpp: In function 'std::pair<int, int> slow()':
horses.cpp:87:9: warning: declaration of 'ind' shadows a global declaration [-Wshadow]
     int ind=0;
         ^~~
horses.cpp:83:18: note: shadowed declaration is here
 int active[nmax],ind=0;
                  ^~~
horses.cpp: In function 'void test(long long int, long long int, long long int&, long long int&)':
horses.cpp:107:24: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
                        ^
horses.cpp:107:37: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
                                     ^
horses.cpp:107:52: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
                                                    ^
horses.cpp:107:65: warning: conversion to 'double' from 'long long int' may alter its value [-Wconversion]
     double p=log10(1.0*a)+log10(1.0*b),q=log10(1.0*c)+log10(1.0*d);
                                                                 ^
horses.cpp: In function 'int query()':
horses.cpp:139:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ind==non_zero.size())
        ~~~^~~~~~~~~~~~~~~~~
horses.cpp:149:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ind!=non_zero.size())mult=query_x(1,0,n-1,0,active[1]-1);
        ~~~^~~~~~~~~~~~~~~~~
horses.cpp:179:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ret;
            ^~~
horses.cpp:118:9: warning: unused variable 'last' [-Wunused-variable]
     int last=n,pos=-1;
         ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 488 KB Output is correct
7 Correct 2 ms 488 KB Output is correct
8 Correct 3 ms 520 KB Output is correct
9 Correct 2 ms 544 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 636 KB Output is correct
13 Correct 2 ms 636 KB Output is correct
14 Correct 2 ms 636 KB Output is correct
15 Correct 2 ms 636 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 732 KB Output is correct
18 Correct 2 ms 732 KB Output is correct
19 Correct 2 ms 732 KB Output is correct
20 Correct 2 ms 732 KB Output is correct

Subtask #2
17.0 / 17.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 49472 KB Output is correct
2 Correct 471 ms 49472 KB Output is correct
3 Correct 485 ms 49472 KB Output is correct
4 Correct 610 ms 49472 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 49472 KB Output is correct
2 Correct 3 ms 49472 KB Output is correct
3 Correct 3 ms 49472 KB Output is correct
4 Correct 2 ms 49472 KB Output is correct
5 Correct 2 ms 49472 KB Output is correct
6 Correct 2 ms 49472 KB Output is correct
7 Correct 2 ms 49472 KB Output is correct
8 Correct 2 ms 49472 KB Output is correct
9 Correct 2 ms 49472 KB Output is correct
10 Correct 2 ms 49472 KB Output is correct
11 Correct 2 ms 49472 KB Output is correct
12 Correct 3 ms 49472 KB Output is correct
13 Correct 3 ms 49472 KB Output is correct
14 Correct 3 ms 49472 KB Output is correct
15 Correct 2 ms 49472 KB Output is correct
16 Correct 2 ms 49472 KB Output is correct
17 Correct 2 ms 49472 KB Output is correct
18 Correct 2 ms 49472 KB Output is correct
19 Correct 3 ms 49472 KB Output is correct
20 Correct 2 ms 49472 KB Output is correct
21 Correct 2 ms 49472 KB Output is correct
22 Correct 2 ms 49472 KB Output is correct
23 Correct 3 ms 49472 KB Output is correct
24 Correct 3 ms 49472 KB Output is correct
25 Correct 5 ms 49472 KB Output is correct
26 Correct 3 ms 49472 KB Output is correct
27 Correct 6 ms 49472 KB Output is correct
28 Correct 5 ms 49472 KB Output is correct
29 Correct 4 ms 49472 KB Output is correct
30 Correct 4 ms 49472 KB Output is correct
31 Correct 6 ms 49472 KB Output is correct
32 Correct 10 ms 49472 KB Output is correct
33 Correct 65 ms 49472 KB Output is correct
34 Correct 64 ms 49472 KB Output is correct
35 Correct 271 ms 63340 KB Output is correct
36 Correct 265 ms 74208 KB Output is correct
37 Correct 123 ms 74208 KB Output is correct
38 Correct 163 ms 74208 KB Output is correct
39 Correct 68 ms 74208 KB Output is correct
40 Correct 264 ms 87436 KB Output is correct
41 Correct 87 ms 87436 KB Output is correct
42 Correct 122 ms 87436 KB Output is correct
43 Correct 275 ms 97824 KB Output is correct
44 Correct 242 ms 104276 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 104276 KB Output is correct
2 Correct 3 ms 104276 KB Output is correct
3 Correct 2 ms 104276 KB Output is correct
4 Correct 2 ms 104276 KB Output is correct
5 Correct 2 ms 104276 KB Output is correct
6 Correct 2 ms 104276 KB Output is correct
7 Correct 2 ms 104276 KB Output is correct
8 Correct 3 ms 104276 KB Output is correct
9 Correct 3 ms 104276 KB Output is correct
10 Correct 2 ms 104276 KB Output is correct
11 Correct 3 ms 104276 KB Output is correct
12 Correct 2 ms 104276 KB Output is correct
13 Correct 3 ms 104276 KB Output is correct
14 Correct 3 ms 104276 KB Output is correct
15 Correct 3 ms 104276 KB Output is correct
16 Correct 3 ms 104276 KB Output is correct
17 Correct 3 ms 104276 KB Output is correct
18 Correct 3 ms 104276 KB Output is correct
19 Correct 3 ms 104276 KB Output is correct
20 Correct 3 ms 104276 KB Output is correct
21 Correct 3 ms 104276 KB Output is correct
22 Correct 3 ms 104276 KB Output is correct
23 Correct 4 ms 104276 KB Output is correct
24 Correct 5 ms 104276 KB Output is correct
25 Correct 5 ms 104276 KB Output is correct
26 Correct 6 ms 104276 KB Output is correct
27 Correct 7 ms 104276 KB Output is correct
28 Correct 7 ms 104276 KB Output is correct
29 Correct 3 ms 104276 KB Output is correct
30 Correct 4 ms 104276 KB Output is correct
31 Correct 6 ms 104276 KB Output is correct
32 Correct 7 ms 104276 KB Output is correct
33 Correct 1006 ms 106944 KB Output is correct
34 Correct 584 ms 119348 KB Output is correct
35 Correct 513 ms 123148 KB Output is correct
36 Correct 706 ms 130752 KB Output is correct
37 Correct 71 ms 130752 KB Output is correct
38 Correct 69 ms 130752 KB Output is correct
39 Correct 269 ms 148672 KB Output is correct
40 Correct 248 ms 159420 KB Output is correct
41 Correct 127 ms 159420 KB Output is correct
42 Correct 151 ms 159420 KB Output is correct
43 Correct 56 ms 159420 KB Output is correct
44 Correct 236 ms 172568 KB Output is correct
45 Correct 87 ms 172568 KB Output is correct
46 Correct 118 ms 172568 KB Output is correct
47 Correct 273 ms 183028 KB Output is correct
48 Correct 241 ms 189408 KB Output is correct
49 Correct 285 ms 189408 KB Output is correct
50 Correct 248 ms 189408 KB Output is correct
51 Correct 507 ms 212416 KB Output is correct
52 Correct 381 ms 223716 KB Output is correct
53 Correct 818 ms 223716 KB Output is correct
54 Correct 584 ms 223716 KB Output is correct
55 Correct 171 ms 223716 KB Output is correct
56 Correct 407 ms 240840 KB Output is correct
57 Correct 442 ms 240840 KB Output is correct
58 Correct 765 ms 240840 KB Output is correct
59 Correct 228 ms 252472 KB Output is correct