Submission #431462

#	Time	Username	Problem	Language	Result	Execution time	Memory
431462		p_square	Horses (IOI15_horses)	C++14	17 / 100	18 ms	10460 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll MOD = 1e9+7, INFTY = 1e9+10;

ll pastbig[30], gopro[35], otmul[35];
ll x[1000], y[1000], n;

struct node
{
    ll bgnum, mx, prod, lr, rr;
    node *lkid, *rkid;

    node(ll a, ll b) {lr = a; rr = b;}
    node() {}
};

node *rt;

void build_seg(node *cur, ll x[], ll y[])
{
    ll l = cur -> lr, r = cur -> rr;
    if(l == r)
    {
        cur -> prod = x[l];
        cur -> mx = y[l];
        cur -> bgnum = 0;
        if(x[l] > 1)
            cur -> bgnum = 1;
        return;
    }

    ll mid = (l+r)/2;
    cur -> lkid = new node(l, mid);
    cur -> rkid = new node(mid+1, r);

    build_seg(cur->lkid, x, y);
    build_seg(cur->rkid, x, y);

    node *lch = cur ->lkid, *rch = cur -> rkid;

    cur -> mx = max(lch -> mx, rch -> mx);
    cur -> bgnum = lch->bgnum + rch->bgnum;
    cur -> prod = lch->prod * rch->prod;
    cur->prod %= MOD;

    //cout<<l<<" "<<r<<" "<<cur->bgnum<<endl;
}

void update_seg(node *cur, ll x[], ll y[], ll ind)
{
    ll l = cur -> lr, r = cur -> rr;
    if(l > ind || r < ind)
        return;
    if(l == r)
    {
        cur -> prod = x[l];
        cur -> mx = y[l];
        cur -> bgnum = 0;
        if(x[l] > 1)
            cur -> bgnum = 1;
        return;
    }

    update_seg(cur->lkid, x, y, ind);
    update_seg(cur->rkid, x, y, ind);

    node *lch = cur ->lkid, *rch = cur -> rkid;

    cur -> mx = max(lch -> mx, rch -> mx);
    cur -> bgnum = lch->bgnum + rch->bgnum;
    cur -> prod = lch->prod * rch->prod;
    cur->prod %= MOD;

    //cout<<l<<" "<<r<<" "<<cur->bgnum<<endl;
}

int qmax_seg(node *cur, int ql, int qr)
{
    if(cur -> lr > qr || cur -> rr < ql)
        return -1;

    if(cur -> lr >= ql && cur -> rr <= qr)
        return cur -> mx;

    int a = qmax_seg(cur->lkid, ql, qr);
    int b = qmax_seg(cur->rkid, ql, qr);
    return max(a, b);
}

int qprod_seg(node *cur, int ql, int qr)
{
    if(cur -> lr > qr || cur -> rr < ql)
        return 1;

    if(cur -> lr >= ql && cur -> rr <= qr)
        return cur -> prod;

    int a = qprod_seg(cur->lkid, ql, qr);
    int b = qprod_seg(cur->rkid, ql, qr);
    return a*b%MOD;
}

int onefy(node *cur, int req)
{
    ll l = cur -> lr, r = cur -> rr;
    if(cur -> bgnum <= req)
        return 0;

    if(l == r)
        return l;

    node *lch = cur ->lkid, *rch = cur -> rkid;
    if(rch -> bgnum > req)
        return onefy(rch, req);
    else
        return onefy(lch, req-rch->bgnum);
}

const ll zero = 0;
int find_ans()
{
    int prev = n, can = 0, curgo, curmul;
    for(int i = 0; i<30; i++)
    {
        gopro[i] = INFTY;
    }
    gopro[0] = 1;
    curgo = 1;
    otmul[0] = qmax_seg(rt, pastbig[0], prev-1);
    curmul = otmul[0];

    for(int i = 0; i<29; i++)
    {
        //cout<<gopro[i]<<" "<<otmul[i]<<" "<<pastbig[i]<<endl;
        //cout<<curgo<<" "<<curmul<<endl;

        gopro[i+1] = gopro[i]*x[pastbig[i]];
        if(gopro[i+1] > INFTY)
            break;
        otmul[i+1] = qmax_seg(rt, pastbig[i+1], pastbig[i]-1);

        if(curmul*gopro[i+1] < otmul[i+1]*curgo)
        {
            curmul = otmul[i+1];
            curgo = gopro[i+1];
            can = i+1;
        }
    }

    //cout<<can<<" "<<otmul[can]<<endl;
    //cout<<qprod_seg(rt, zero, pastbig[can]);
    return otmul[can]*qprod_seg(rt, zero, pastbig[can])%MOD;
}

int init(int N, int X[], int Y[])
{
    rt = new node(0, N-1);
    n = N;
    for(int i = 0; i<N; i++)
    {
        x[i] = X[i];
        y[i] = Y[i];
    }
    build_seg(rt, x, y);
    for(int i = 0; i<30; i++)
    {
        pastbig[i] = onefy(rt, i);
    }
    return find_ans();
}

int updateX(int pos, int val)
{
    //First, update seg
    int oldval = x[pos];
    x[pos] = val;
    update_seg(rt, x, y, pos);

    //Now, update pastbig
    int onemod = 300;
    if(val == 1 && oldval > 1)
    {
        for(int i = 0; i<30; i++)
        {
            if(pastbig[i] == pos)
            {
                onemod = i;
                break;
            }
        }
        for(int i = onemod; i<29; i++)
        {
            pastbig[i] = pastbig[i+1];
        }
        pastbig[29] = onefy(rt, 29);
    }
    if(oldval == 1 && val > 1)
    {
        for(int i = 0; i<30; i++)
        {
            if(pastbig[i] < pos)
            {
                onemod = i;
                break;
            }
        }
        for(int i = 29; i>onemod; i--)
        {
            pastbig[i] = pastbig[i-1];
        }
        if(onemod != 300)
            pastbig[onemod] = pos;

        //cout<<"MOD"<<onemod<<endl;
    }

    /*
    for(int i = 0; i<10; i++)
    {
        cout<<pastbig[i]<<" ";
    }
    */

    return find_ans();
}

int updateY(int pos, int val)
{
    y[pos] = val;
    update_seg(rt, x, y, pos);
    return find_ans();
}

Compilation message (stderr)

horses.cpp: In function 'void build_seg(node*, long long int*, long long int*)':
horses.cpp:24:38: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   24 | void build_seg(node *cur, ll x[], ll y[])
      |                                      ^
horses.cpp:11:13: note: shadowed declaration is here
   11 | ll x[1000], y[1000], n;
      |             ^
horses.cpp:24:30: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   24 | void build_seg(node *cur, ll x[], ll y[])
      |                              ^
horses.cpp:11:4: note: shadowed declaration is here
   11 | ll x[1000], y[1000], n;
      |    ^
horses.cpp: In function 'void update_seg(node*, long long int*, long long int*, long long int)':
horses.cpp:54:39: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   54 | void update_seg(node *cur, ll x[], ll y[], ll ind)
      |                                       ^
horses.cpp:11:13: note: shadowed declaration is here
   11 | ll x[1000], y[1000], n;
      |             ^
horses.cpp:54:31: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   54 | void update_seg(node *cur, ll x[], ll y[], ll ind)
      |                               ^
horses.cpp:11:4: note: shadowed declaration is here
   11 | ll x[1000], y[1000], n;
      |    ^
horses.cpp: In function 'int qmax_seg(node*, int, int)':
horses.cpp:88:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   88 |         return cur -> mx;
      |                ~~~~~~~^~
horses.cpp: In function 'int qprod_seg(node*, int, int)':
horses.cpp:101:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  101 |         return cur -> prod;
      |                ~~~~~~~^~~~
horses.cpp: In function 'int onefy(node*, int)':
horses.cpp:115:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  115 |         return l;
      |                ^
horses.cpp:121:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  121 |         return onefy(lch, req-rch->bgnum);
      |                           ~~~^~~~~~~~~~~
horses.cpp: In function 'int find_ans()':
horses.cpp:127:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |     int prev = n, can = 0, curgo, curmul;
      |                ^
horses.cpp:134:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  134 |     otmul[0] = qmax_seg(rt, pastbig[0], prev-1);
      |                             ~~~~~~~~~^
horses.cpp:135:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  135 |     curmul = otmul[0];
      |              ~~~~~~~^
horses.cpp:145:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  145 |         otmul[i+1] = qmax_seg(rt, pastbig[i+1], pastbig[i]-1);
      |                                   ~~~~~~~~~~~^
horses.cpp:145:59: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  145 |         otmul[i+1] = qmax_seg(rt, pastbig[i+1], pastbig[i]-1);
      |                                                 ~~~~~~~~~~^~
horses.cpp:149:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  149 |             curmul = otmul[i+1];
      |                      ~~~~~~~~~^
horses.cpp:150:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  150 |             curgo = gopro[i+1];
      |                     ~~~~~~~~~^
horses.cpp:157:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  157 |     return otmul[can]*qprod_seg(rt, zero, pastbig[can])%MOD;
      |                                           ~~~~~~~~~~~^
horses.cpp:157:56: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  157 |     return otmul[can]*qprod_seg(rt, zero, pastbig[can])%MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:180:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  180 |     int oldval = x[pos];
      |                  ~~~~~^

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