oj.uz

Submission #431540

# Submission time Handle Problem Language Result Execution time Memory
431540 2021-06-17T12:48:56 Z p_square Horses (IOI15_horses) C++14
100 / 100
 1150 ms 88272 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 252 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 224 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 2 ms 456 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 5 ms 460 KB Output is correct
28 Correct 2 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 444 KB Output is correct
31 Correct 4 ms 444 KB Output is correct
32 Correct 4 ms 460 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 77196 KB Output is correct
2 Correct 345 ms 88172 KB Output is correct
3 Correct 386 ms 79360 KB Output is correct
4 Correct 417 ms 83208 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 484 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 22 ms 460 KB Output is correct
27 Correct 6 ms 460 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 4 ms 460 KB Output is correct
32 Correct 5 ms 484 KB Output is correct
33 Correct 143 ms 75188 KB Output is correct
34 Correct 116 ms 78596 KB Output is correct
35 Correct 146 ms 85544 KB Output is correct
36 Correct 151 ms 85552 KB Output is correct
37 Correct 191 ms 76832 KB Output is correct
38 Correct 109 ms 77832 KB Output is correct
39 Correct 118 ms 76692 KB Output is correct
40 Correct 120 ms 80668 KB Output is correct
41 Correct 124 ms 76780 KB Output is correct
42 Correct 156 ms 76752 KB Output is correct
43 Correct 103 ms 81016 KB Output is correct
44 Correct 110 ms 80948 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 444 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 3 ms 444 KB Output is correct
26 Correct 2 ms 444 KB Output is correct
27 Correct 5 ms 460 KB Output is correct
28 Correct 4 ms 460 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 4 ms 460 KB Output is correct
32 Correct 5 ms 460 KB Output is correct
33 Correct 753 ms 77784 KB Output is correct
34 Correct 347 ms 88272 KB Output is correct
35 Correct 376 ms 79336 KB Output is correct
36 Correct 410 ms 83232 KB Output is correct
37 Correct 235 ms 78716 KB Output is correct
38 Correct 120 ms 78776 KB Output is correct
39 Correct 158 ms 85608 KB Output is correct
40 Correct 158 ms 85548 KB Output is correct
41 Correct 303 ms 76828 KB Output is correct
42 Correct 106 ms 77720 KB Output is correct
43 Correct 115 ms 76724 KB Output is correct
44 Correct 109 ms 80632 KB Output is correct
45 Correct 121 ms 76884 KB Output is correct
46 Correct 160 ms 76844 KB Output is correct
47 Correct 120 ms 80940 KB Output is correct
48 Correct 106 ms 80952 KB Output is correct
49 Correct 369 ms 80616 KB Output is correct
50 Correct 333 ms 80616 KB Output is correct
51 Correct 317 ms 87380 KB Output is correct
52 Correct 212 ms 87000 KB Output is correct
53 Correct 1150 ms 78972 KB Output is correct
54 Correct 375 ms 79552 KB Output is correct
55 Correct 271 ms 77804 KB Output is correct
56 Correct 246 ms 82408 KB Output is correct
57 Correct 590 ms 78316 KB Output is correct
58 Correct 776 ms 78920 KB Output is correct
59 Correct 113 ms 81004 KB Output is correct