Submission #731341

#	Time	Username	Problem	Language	Result	Execution time	Memory
731341		lucri	Horses (IOI15_horses)	C++17	77 / 100	1566 ms	38548 KiB

horses

    #include "horses.h"
    #include <bits/stdc++.h>
    #define MOD 1000000007
    long long aintx[2000010],x[500010];
    long long ainty[2000010],y[500010];
    long long aintprod[2000010],n;
     
    void initializeaintx(int poz,int b,int e)
    {
        if(b==e)
        {
            aintx[poz]=(x[b]!=1);
            return;
        }
        initializeaintx(poz*2,b,(b+e)/2);
        initializeaintx(poz*2+1,(b+e)/2+1,e);
        aintx[poz]=(aintx[poz*2]|aintx[poz*2+1]);
    }
    void updateaintx(int poz,int b,int e,int pozm,int val)
    {
        if(e<pozm||b>pozm)
            return;
        if(b==e)
        {
            aintx[poz]=(x[b]!=1);
            return;
        }
        updateaintx(poz*2,b,(b+e)/2,pozm,val);
        updateaintx(poz*2+1,(b+e)/2+1,e,pozm,val);
        aintx[poz]=(aintx[poz*2]|aintx[poz*2+1]);
    }
     
    void initializeainty(int poz,int b,int e)
    {
        if(b==e)
        {
            ainty[poz]=y[b];
            return;
        }
        initializeainty(poz*2,b,(b+e)/2);
        initializeainty(poz*2+1,(b+e)/2+1,e);
        ainty[poz]=std::max(ainty[poz*2],ainty[poz*2+1]);
    }
    void updateainty(int poz,int b,int e,int pozm,int val)
    {
        if(e<pozm||b>pozm)
            return;
        if(b==e)
        {
            ainty[poz]=y[b];
            return;
        }
        updateainty(poz*2,b,(b+e)/2,pozm,val);
        updateainty(poz*2+1,(b+e)/2+1,e,pozm,val);
        ainty[poz]=std::max(ainty[poz*2],ainty[poz*2+1]);
    }
     
    void initializeaintprod(int poz,int b,int e)
    {
        if(b==e)
        {
            aintprod[poz]=x[b];
            return;
        }
        initializeaintprod(poz*2,b,(b+e)/2);
        initializeaintprod(poz*2+1,(b+e)/2+1,e);
        aintprod[poz]=aintprod[poz*2]*aintprod[poz*2+1]%MOD;
    }
    void updateaintprod(int poz,int b,int e,int pozm,int val)
    {
        if(e<pozm||b>pozm)
            return;
        if(b==e)
        {
            aintprod[poz]=x[b];
            return;
        }
        updateaintprod(poz*2,b,(b+e)/2,pozm,val);
        updateaintprod(poz*2+1,(b+e)/2+1,e,pozm,val);
        aintprod[poz]=aintprod[poz*2]*aintprod[poz*2+1]%MOD;
    }
     
    long long difde0(int poz,int b,int e,int ei)
    {
        if(b>=ei)
            return 0;
        if(aintx[poz]==0)
            return 0;
        if(b==e)
            return b;
        int poza=difde0(poz*2+1,(b+e)/2+1,e,ei);
        if(poza)
            return poza;
        return difde0(poz*2,b,(b+e)/2,ei);
    }
    long long maxim(int poz,int b,int e,int bi,int ei)
    {
        if(b>ei||e<bi)
            return 0;
        if(bi<=b&&e<=ei)
            return ainty[poz];
        return std::max(maxim(poz*2,b,(b+e)/2,bi,ei),maxim(poz*2+1,(b+e)/2+1,e,bi,ei));
    }
    long long produs(int poz,int b,int e,int bi,int ei)
    {
        if(b>ei||e<bi)
            return 1;
        if(bi<=b&&e<=ei)
            return aintprod[poz];
        return produs(poz*2,b,(b+e)/2,bi,ei)*produs(poz*2+1,(b+e)/2+1,e,bi,ei)%MOD;
    }
     
     
    long long calculeaza()
    {
        long long prod=x[n]*y[n],pozant=n;
        while(prod<1000000000&&pozant)
        {
            int pozac=pozant;
            pozant=difde0(1,1,n,pozant);
            long long vmax=maxim(1,1,n,pozant,pozac-1);
            if(vmax>prod)
                prod=vmax;
            if(pozant!=0)
                prod*=x[pozant];
        }
        prod%=MOD;
        long long ans=prod*produs(1,1,n,1,pozant-1)%MOD;
        return ans;
    }
     
    int init(int N, int X[], int Y[])
    {
        n=N;
        for(int i=1;i<=N;++i)
        {
            x[i]=X[i-1];
            y[i]=Y[i-1];
        }
        initializeaintx(1,1,N);
        initializeainty(1,1,N);
        initializeaintprod(1,1,N);
        return calculeaza();
    }
     
    int updateX(int pos, int val)
    {
        ++pos;
        x[pos]=val;
        updateaintx(1,1,n,pos,val);
        updateaintprod(1,1,n,pos,val);
        calculeaza();
    	return calculeaza();
    }
     
    int updateY(int pos, int val)
    {
        ++pos;
        y[pos]=val;
        updateainty(1,1,n,pos,val);
        calculeaza();
    	return calculeaza();
    }

Compilation message (stderr)

horses.cpp: In function 'long long int difde0(int, int, int, int)':
horses.cpp:91:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |         int poza=difde0(poz*2+1,(b+e)/2+1,e,ei);
      |                  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp: In function 'long long int calculeaza()':
horses.cpp:119:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |             int pozac=pozant;
      |                       ^~~~~~
horses.cpp:120:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |             pozant=difde0(1,1,n,pozant);
      |                               ^
horses.cpp:120:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  120 |             pozant=difde0(1,1,n,pozant);
      |                                 ^~~~~~
horses.cpp:121:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |             long long vmax=maxim(1,1,n,pozant,pozac-1);
      |                                      ^
horses.cpp:121:40: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |             long long vmax=maxim(1,1,n,pozant,pozac-1);
      |                                        ^~~~~~
horses.cpp:128:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |         long long ans=prod*produs(1,1,n,1,pozant-1)%MOD;
      |                                       ^
horses.cpp:128:49: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |         long long ans=prod*produs(1,1,n,1,pozant-1)%MOD;
      |                                           ~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:143:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  143 |         return calculeaza();
      |                ~~~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:150:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  150 |         updateaintx(1,1,n,pos,val);
      |                         ^
horses.cpp:151:28: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  151 |         updateaintprod(1,1,n,pos,val);
      |                            ^
horses.cpp:153:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  153 |      return calculeaza();
      |             ~~~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:160:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  160 |         updateainty(1,1,n,pos,val);
      |                         ^
horses.cpp:162:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  162 |      return calculeaza();
      |             ~~~~~~~~~~^~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 0 / 23