oj.uz

Submission #66960

# Submission time Handle Problem Language Result Execution time Memory
66960 2018-08-12T21:14:05 Z MKopchev Horses (IOI15_horses) C++14
37 / 100
 630 ms 49688 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)
{
    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/1e6)
        {
            maxi=now;
            ind=i;
        }
    }
    long long res=y[ind];
    for(int i=0;i<=ind;i++)
    {
        res=res*x[i]%mod;
    }
    return {res,ind};
}
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;
    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;
        maxi=max(maxi,prod*query_y(1,0,n-1,active[i],active[i+1]-1));
    }

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

    //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);

    long long ret;
    if(bigger(a,b,maxi))ret=a%mod*b%mod*mult%mod;
    else ret=maxi%mod*mult%mod;
    if(n<=1000)
    {
        if(ret!=slow().first)
        {
            if(bigger(a,b,maxi))
            {
            assert(slow().second==active[ind]);
            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();
}
/*
int X[]={1,1,3};
int Y[]={1,4,1};
int main()
{
    cout<<init(3,X,Y)<<endl;
    cout<<updateY(1,2)<<endl;
    cout<<updateX(2,4)<<endl;
}
*/

Compilation message

horses.cpp: In function 'int query_x(int, int, int, int, int)':
horses.cpp:34: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:39: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:68: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:85:9: warning: declaration of 'ind' shadows a global declaration [-Wshadow]
     int ind=0;
         ^~~
horses.cpp:81:18: note: shadowed declaration is here
 int active[nmax],ind=0;
                  ^~~
horses.cpp: In function 'int query()':
horses.cpp:126:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ind==non_zero.size())
        ~~~^~~~~~~~~~~~~~~~~
horses.cpp:134: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:155:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return ret;
            ^~~
horses.cpp:107: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 3 ms 376 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Correct 3 ms 548 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 3 ms 548 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 4 ms 720 KB Output is correct
10 Correct 3 ms 720 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 3 ms 720 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 2 ms 720 KB Output is correct
15 Correct 3 ms 720 KB Output is correct
16 Correct 3 ms 720 KB Output is correct
17 Correct 3 ms 720 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 720 KB Output is correct
20 Correct 3 ms 720 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 720 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 3 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 2 ms 720 KB Output is correct
8 Correct 2 ms 720 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 3 ms 720 KB Output is correct
12 Correct 2 ms 720 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Correct 2 ms 720 KB Output is correct
15 Correct 3 ms 720 KB Output is correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 3 ms 720 KB Output is correct
18 Correct 3 ms 720 KB Output is correct
19 Correct 3 ms 720 KB Output is correct
20 Correct 3 ms 720 KB Output is correct
21 Correct 3 ms 720 KB Output is correct
22 Correct 3 ms 720 KB Output is correct
23 Correct 73 ms 772 KB Output is correct
24 Correct 69 ms 772 KB Output is correct
25 Correct 82 ms 772 KB Output is correct
26 Correct 74 ms 784 KB Output is correct
27 Correct 48 ms 784 KB Output is correct
28 Correct 87 ms 796 KB Output is correct
29 Correct 41 ms 812 KB Output is correct
30 Correct 46 ms 812 KB Output is correct
31 Runtime error 30 ms 940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 49556 KB Output is correct
2 Correct 512 ms 49688 KB Output is correct
3 Correct 512 ms 49688 KB Output is correct
4 Correct 576 ms 49688 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 49688 KB Output is correct
2 Correct 3 ms 49688 KB Output is correct
3 Correct 3 ms 49688 KB Output is correct
4 Correct 3 ms 49688 KB Output is correct
5 Correct 2 ms 49688 KB Output is correct
6 Correct 3 ms 49688 KB Output is correct
7 Correct 2 ms 49688 KB Output is correct
8 Correct 2 ms 49688 KB Output is correct
9 Correct 2 ms 49688 KB Output is correct
10 Correct 3 ms 49688 KB Output is correct
11 Correct 2 ms 49688 KB Output is correct
12 Correct 2 ms 49688 KB Output is correct
13 Correct 2 ms 49688 KB Output is correct
14 Correct 2 ms 49688 KB Output is correct
15 Correct 2 ms 49688 KB Output is correct
16 Correct 2 ms 49688 KB Output is correct
17 Correct 2 ms 49688 KB Output is correct
18 Correct 2 ms 49688 KB Output is correct
19 Correct 3 ms 49688 KB Output is correct
20 Correct 3 ms 49688 KB Output is correct
21 Correct 2 ms 49688 KB Output is correct
22 Correct 3 ms 49688 KB Output is correct
23 Correct 67 ms 49688 KB Output is correct
24 Correct 65 ms 49688 KB Output is correct
25 Correct 81 ms 49688 KB Output is correct
26 Correct 83 ms 49688 KB Output is correct
27 Correct 47 ms 49688 KB Output is correct
28 Correct 83 ms 49688 KB Output is correct
29 Correct 34 ms 49688 KB Output is correct
30 Correct 48 ms 49688 KB Output is correct
31 Runtime error 46 ms 49688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 49688 KB Output is correct
2 Correct 3 ms 49688 KB Output is correct
3 Correct 2 ms 49688 KB Output is correct
4 Correct 3 ms 49688 KB Output is correct
5 Correct 2 ms 49688 KB Output is correct
6 Correct 2 ms 49688 KB Output is correct
7 Correct 3 ms 49688 KB Output is correct
8 Correct 3 ms 49688 KB Output is correct
9 Correct 2 ms 49688 KB Output is correct
10 Correct 2 ms 49688 KB Output is correct
11 Correct 2 ms 49688 KB Output is correct
12 Correct 2 ms 49688 KB Output is correct
13 Correct 2 ms 49688 KB Output is correct
14 Correct 3 ms 49688 KB Output is correct
15 Correct 4 ms 49688 KB Output is correct
16 Correct 3 ms 49688 KB Output is correct
17 Correct 4 ms 49688 KB Output is correct
18 Correct 2 ms 49688 KB Output is correct
19 Correct 8 ms 49688 KB Output is correct
20 Correct 2 ms 49688 KB Output is correct
21 Correct 2 ms 49688 KB Output is correct
22 Correct 2 ms 49688 KB Output is correct
23 Correct 68 ms 49688 KB Output is correct
24 Correct 67 ms 49688 KB Output is correct
25 Correct 89 ms 49688 KB Output is correct
26 Correct 80 ms 49688 KB Output is correct
27 Correct 46 ms 49688 KB Output is correct
28 Correct 77 ms 49688 KB Output is correct
29 Correct 35 ms 49688 KB Output is correct
30 Correct 48 ms 49688 KB Output is correct
31 Runtime error 44 ms 49688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -