Submission #431540

#	Time	Username	Problem	Language	Result	Execution time	Memory
431540		p_square	Horses (IOI15_horses)	C++14	100 / 100	1150 ms	88272 KiB

horses

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

using namespace std;

#define ll long long

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

ll pastbig[32], gopro[35], otmul[35];
ll x[500001], y[500001], 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;
}

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

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

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

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

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

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

ll onefy(node *cur, ll 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;
ll find_ans()
{
    ll prev = n, can = 0, curgo, curmul;
    for(int i = 0; i<32; 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<31; 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])<<endl;
    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<32; i++)
    {
        pastbig[i] = onefy(rt, i);
    }
    return find_ans();
}

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

    //Now, update pastbig
    ll onemod = 300;
    if(val == 1 && oldval > 1)
    {
        for(int i = 0; i<32; i++)
        {
            if(pastbig[i] == pos)
            {
                onemod = i;
                break;
            }
        }
        for(int i = onemod; i<31; i++)
        {
            pastbig[i] = pastbig[i+1];
        }
        pastbig[31] = onefy(rt, 31);
    }
    if(oldval == 1 && val > 1)
    {
        for(int i = 0; i<32; i++)
        {
            if(pastbig[i] < pos)
            {
                onemod = i;
                break;
            }
        }
        for(int i = 31; 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:15: note: shadowed declaration is here
   11 | ll x[500001], y[500001], 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[500001], y[500001], 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:15: note: shadowed declaration is here
   11 | ll x[500001], y[500001], 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[500001], y[500001], n;
      |    ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:174:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  174 |     return find_ans();
      |            ~~~~~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:196:21: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  196 |         for(int i = onemod; i<31; i++)
      |                     ^~~~~~
horses.cpp:229:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  229 |     return find_ans();
      |            ~~~~~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:236:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  236 |     return find_ans();
      |            ~~~~~~~~^~

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