oj.uz

Submission #66954

# Submission time Handle Problem Language Result Execution time Memory
66954 2018-08-12T20:51:07 Z MKopchev Horses (IOI15_horses) C++14
37 / 100
 657 ms 49696 KB 
#include<bits/stdc++.h>
#include "horses.h"
using namespace std;
const int nmax=5e5+42,mod=1e9+7,inf=1e9;
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=1;
    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;
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);

    if(bigger(a,b,maxi))return a%mod*b%mod*mult%mod;
    return maxi%mod*mult%mod;
}

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[]={2,1,3};
int Y[]={3,4,1};
int main()
{
    cout<<init(3,X,Y)<<endl;
    cout<<updateY(1,2)<<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 'int query()':
horses.cpp:105:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ind==non_zero.size())
        ~~~^~~~~~~~~~~~~~~~~
horses.cpp:113: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:118:48: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     if(bigger(a,b,maxi))return a%mod*b%mod*mult%mod;
                                ~~~~~~~~~~~~~~~~^~~~
horses.cpp:119:25: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return maxi%mod*mult%mod;
            ~~~~~~~~~~~~~^~~~
horses.cpp:86: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 376 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 3 ms 644 KB Output is correct
12 Correct 2 ms 644 KB Output is correct
13 Correct 3 ms 680 KB Output is correct
14 Correct 2 ms 680 KB Output is correct
15 Correct 2 ms 680 KB Output is correct
16 Correct 3 ms 680 KB Output is correct
17 Correct 2 ms 680 KB Output is correct
18 Correct 3 ms 680 KB Output is correct
19 Correct 3 ms 680 KB Output is correct
20 Correct 3 ms 680 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 680 KB Output is correct
2 Correct 2 ms 680 KB Output is correct
3 Correct 2 ms 680 KB Output is correct
4 Correct 3 ms 680 KB Output is correct
5 Correct 3 ms 680 KB Output is correct
6 Correct 3 ms 680 KB Output is correct
7 Correct 3 ms 680 KB Output is correct
8 Correct 4 ms 680 KB Output is correct
9 Correct 3 ms 680 KB Output is correct
10 Correct 2 ms 680 KB Output is correct
11 Correct 3 ms 680 KB Output is correct
12 Correct 2 ms 680 KB Output is correct
13 Correct 3 ms 680 KB Output is correct
14 Correct 2 ms 680 KB Output is correct
15 Correct 2 ms 680 KB Output is correct
16 Correct 2 ms 680 KB Output is correct
17 Correct 2 ms 680 KB Output is correct
18 Correct 2 ms 680 KB Output is correct
19 Correct 3 ms 680 KB Output is correct
20 Correct 3 ms 680 KB Output is correct
21 Correct 3 ms 680 KB Output is correct
22 Correct 3 ms 680 KB Output is correct
23 Correct 3 ms 680 KB Output is correct
24 Correct 4 ms 744 KB Output is correct
25 Correct 4 ms 824 KB Output is correct
26 Correct 4 ms 872 KB Output is correct
27 Correct 6 ms 872 KB Output is correct
28 Correct 4 ms 932 KB Output is correct
29 Correct 4 ms 932 KB Output is correct
30 Correct 4 ms 980 KB Output is correct
31 Incorrect 4 ms 980 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 49680 KB Output is correct
2 Correct 462 ms 49696 KB Output is correct
3 Correct 455 ms 49696 KB Output is correct
4 Correct 565 ms 49696 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 49696 KB Output is correct
2 Correct 2 ms 49696 KB Output is correct
3 Correct 2 ms 49696 KB Output is correct
4 Correct 2 ms 49696 KB Output is correct
5 Correct 2 ms 49696 KB Output is correct
6 Correct 25 ms 49696 KB Output is correct
7 Correct 2 ms 49696 KB Output is correct
8 Correct 3 ms 49696 KB Output is correct
9 Correct 2 ms 49696 KB Output is correct
10 Correct 2 ms 49696 KB Output is correct
11 Correct 2 ms 49696 KB Output is correct
12 Correct 3 ms 49696 KB Output is correct
13 Correct 3 ms 49696 KB Output is correct
14 Correct 2 ms 49696 KB Output is correct
15 Correct 2 ms 49696 KB Output is correct
16 Correct 2 ms 49696 KB Output is correct
17 Correct 2 ms 49696 KB Output is correct
18 Correct 3 ms 49696 KB Output is correct
19 Correct 3 ms 49696 KB Output is correct
20 Correct 2 ms 49696 KB Output is correct
21 Correct 3 ms 49696 KB Output is correct
22 Correct 3 ms 49696 KB Output is correct
23 Correct 4 ms 49696 KB Output is correct
24 Correct 4 ms 49696 KB Output is correct
25 Correct 5 ms 49696 KB Output is correct
26 Correct 4 ms 49696 KB Output is correct
27 Correct 6 ms 49696 KB Output is correct
28 Correct 4 ms 49696 KB Output is correct
29 Correct 4 ms 49696 KB Output is correct
30 Correct 3 ms 49696 KB Output is correct
31 Incorrect 5 ms 49696 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 49696 KB Output is correct
2 Correct 3 ms 49696 KB Output is correct
3 Correct 2 ms 49696 KB Output is correct
4 Correct 2 ms 49696 KB Output is correct
5 Correct 2 ms 49696 KB Output is correct
6 Correct 3 ms 49696 KB Output is correct
7 Correct 3 ms 49696 KB Output is correct
8 Correct 2 ms 49696 KB Output is correct
9 Correct 2 ms 49696 KB Output is correct
10 Correct 2 ms 49696 KB Output is correct
11 Correct 2 ms 49696 KB Output is correct
12 Correct 2 ms 49696 KB Output is correct
13 Correct 2 ms 49696 KB Output is correct
14 Correct 2 ms 49696 KB Output is correct
15 Correct 3 ms 49696 KB Output is correct
16 Correct 2 ms 49696 KB Output is correct
17 Correct 2 ms 49696 KB Output is correct
18 Correct 3 ms 49696 KB Output is correct
19 Correct 2 ms 49696 KB Output is correct
20 Correct 2 ms 49696 KB Output is correct
21 Correct 3 ms 49696 KB Output is correct
22 Correct 2 ms 49696 KB Output is correct
23 Correct 3 ms 49696 KB Output is correct
24 Correct 3 ms 49696 KB Output is correct
25 Correct 6 ms 49696 KB Output is correct
26 Correct 4 ms 49696 KB Output is correct
27 Correct 6 ms 49696 KB Output is correct
28 Correct 4 ms 49696 KB Output is correct
29 Correct 4 ms 49696 KB Output is correct
30 Correct 4 ms 49696 KB Output is correct
31 Incorrect 4 ms 49696 KB Output isn't correct
32 Halted 0 ms 0 KB -