oj.uz

Submission #432885

# Submission time Handle Problem Language Result Execution time Memory
432885 2021-06-18T14:38:05 Z daniel920712 Horses (IOI15_horses) C++14
100 / 100
 1350 ms 111724 KB 
#include "horses.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
using namespace std;
long long XX[500005];
long long YY[500005];
long long how[500005]={0};
long long MOD=1e9+7;
long long N;
set < long long > all;
struct A
{
    long long l,r;
    long long con;
    long long big;
    A* nxl,*nxr;
    void build(long long ll,long long rr)
    {
        l=ll;
        r=rr;
        if(ll+1==rr)
        {
            con=XX[ll];
            big=YY[ll];
            return;
        }
        nxl=(A*) malloc(sizeof(A));
        nxr=(A*) malloc(sizeof(A));
        nxl->build(ll,(ll+rr)/2);
        nxr->build((ll+rr)/2,rr);
        con=nxl->con*nxr->con%MOD;
        big=max(nxl->big,nxr->big);
    }
    void cha(long long where,long long tt)
    {
        if(l==where&&r==where+1)
        {
            con=tt;
            return;
        }
        if(where<(l+r)/2) nxl->cha(where,tt);
        else nxr->cha(where,tt);
        con=nxl->con*nxr->con%MOD;
    }
    long long Find(long long ll,long long rr)
    {
        if(ll==l&&rr==r) return con;
        if(rr<=(l+r)/2) return nxl->Find(ll,rr);
        if(ll>=(l+r)/2) return nxr->Find(ll,rr);
        return nxl->Find(ll,(l+r)/2)*nxr->Find((l+r)/2,rr)%MOD;
    }
    void cha2(long long where,long long tt)
    {
        if(l==where&&r==where+1)
        {
            big=tt;
            return;
        }
        if(where<(l+r)/2) nxl->cha2(where,tt);
        else nxr->cha2(where,tt);
        big=max(nxl->big,nxr->big);
    }
    long long Find2(long long ll,long long rr)
    {
        if(ll==l&&rr==r) return big;
        if(rr<=(l+r)/2) return nxl->Find2(ll,rr);
        if(ll>=(l+r)/2) return nxr->Find2(ll,rr);
        return max(nxl->Find2(ll,(l+r)/2),nxr->Find2((l+r)/2,rr));
    }
};
A* root;
int init(int N, int X[], int Y[])
{
    all.insert(-1);
    long long ans=0,t=1,i,now=0,xx,tt,aa;
    ::N=N;
    for(i=0;i<N;i++)
    {
        XX[i]=(long long) X[i];
        YY[i]=(long long) Y[i];
        if(XX[i]>=2) all.insert(i);
    }
    root=(A*)malloc(sizeof(A));
    root->build(0,N);
    now=YY[N-1];
    t=YY[N-1];
    now*=XX[N-1];
    ans=t*root->Find(0,N)%MOD;
    t*=XX[N-1];
    xx=N-1;
    while(now<=1000000000)
    {
        tt=*prev(all.lower_bound(xx));
        if(tt==-1)
        {
            if(xx)
            {
                aa=root->Find2(0,xx);
                if(aa>now)
                {
                    now=aa;
                    t=aa;
                }
                ans=now;
            }
            break;
        }
        else
        {
            aa=root->Find2(tt,xx);
            if(aa>now)
            {
                now=aa;
                t=aa;
            }
            //printf("%lld %lld %lld %lld \n",t,now,tt,xx);
            ans=t*root->Find(0,tt+1)%MOD;
            if(now<1000000000) now*=XX[tt];
            else break;
            t*=XX[tt];
            t%=MOD;
            xx=tt;
        }

    }


	return (int) ans;
}

int updateX(int pos, int val)
{
    long long ans=0,t=1,i,now=0,xx,tt,aa;
    if(XX[pos]>=2) all.erase(pos);
    XX[pos]=(long long) val;
    if(XX[pos]>=2) all.insert(pos);
    root->cha(pos,val);
    now=YY[N-1];
    t=YY[N-1];
    now*=XX[N-1];
    ans=t*root->Find(0,N)%MOD;
    t*=XX[N-1];
    xx=N-1;
    while(now<=1000000000)
    {
        tt=*prev(all.lower_bound(xx));
        if(tt==-1)
        {
            if(xx)
            {
                aa=root->Find2(0,xx);
                if(aa>now)
                {
                    now=aa;
                    t=aa;
                }
                ans=now;
            }
            break;
        }
        else
        {
            aa=root->Find2(tt,xx);
            if(aa>now)
            {
                now=aa;
                t=aa;
            }
            //printf("%lld %lld %lld %lld \n",t,now,tt,xx);
            ans=t*root->Find(0,tt+1)%MOD;
            if(now<1000000000) now*=XX[tt];
            else break;
            t*=XX[tt];
            t%=MOD;
            xx=tt;
        }

    }


	return (int) ans;
}

int updateY(int pos, int val)
{
    long long ans=0,t=1,i,now=0,xx,tt,aa;
    YY[pos]=(long long) val;
    root->cha2(pos,val);
    now=YY[N-1];
    t=YY[N-1];
    now*=XX[N-1];
    ans=t*root->Find(0,N)%MOD;
    t*=XX[N-1];
    xx=N-1;
    while(now<=1000000000)
    {
        tt=*prev(all.lower_bound(xx));
        if(tt==-1)
        {
            if(xx)
            {
                aa=root->Find2(0,xx);
                if(aa>now)
                {
                    now=aa;
                    t=aa;
                }
                ans=now;
            }
            break;
        }
        else
        {
            aa=root->Find2(tt,xx);
            if(aa>now)
            {
                now=aa;
                t=aa;
            }
            //printf("%lld %lld %lld %lld \n",t,now,tt,xx);
            ans=t*root->Find(0,tt+1)%MOD;
            if(now<1000000000) now*=XX[tt];
            else break;
            t*=XX[tt];
            t%=MOD;
            xx=tt;
        }

    }


	return (int) ans;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:74:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   74 | int init(int N, int X[], int Y[])
      |          ~~~~^
horses.cpp:11:11: note: shadowed declaration is here
   11 | long long N;
      |           ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:135:25: warning: unused variable 'i' [-Wunused-variable]
  135 |     long long ans=0,t=1,i,now=0,xx,tt,aa;
      |                         ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:188:25: warning: unused variable 'i' [-Wunused-variable]
  188 |     long long ans=0,t=1,i,now=0,xx,tt,aa;
      |                         ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 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 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 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 0 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 0 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 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 0 ms 204 KB Output is correct
10 Correct 0 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 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 0 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 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 5 ms 436 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 1 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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1329 ms 99172 KB Output is correct
2 Correct 496 ms 111724 KB Output is correct
3 Correct 559 ms 102828 KB Output is correct
4 Correct 528 ms 106772 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 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 0 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 0 ms 204 KB Output is correct
17 Correct 0 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 0 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 256 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 5 ms 460 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 1 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 106 ms 78760 KB Output is correct
34 Correct 97 ms 78740 KB Output is correct
35 Correct 270 ms 109124 KB Output is correct
36 Correct 245 ms 108980 KB Output is correct
37 Correct 186 ms 76868 KB Output is correct
38 Correct 177 ms 89696 KB Output is correct
39 Correct 87 ms 76612 KB Output is correct
40 Correct 236 ms 104052 KB Output is correct
41 Correct 122 ms 76856 KB Output is correct
42 Correct 148 ms 76828 KB Output is correct
43 Correct 225 ms 104516 KB Output is correct
44 Correct 222 ms 104444 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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 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 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 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 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 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 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 1 ms 460 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 4 ms 440 KB Output is correct
32 Correct 5 ms 444 KB Output is correct
33 Correct 1350 ms 102884 KB Output is correct
34 Correct 481 ms 111680 KB Output is correct
35 Correct 608 ms 102956 KB Output is correct
36 Correct 621 ms 106716 KB Output is correct
37 Correct 104 ms 78788 KB Output is correct
38 Correct 96 ms 78764 KB Output is correct
39 Correct 321 ms 109008 KB Output is correct
40 Correct 256 ms 108996 KB Output is correct
41 Correct 182 ms 76888 KB Output is correct
42 Correct 179 ms 89672 KB Output is correct
43 Correct 84 ms 76712 KB Output is correct
44 Correct 239 ms 104256 KB Output is correct
45 Correct 123 ms 76776 KB Output is correct
46 Correct 148 ms 76760 KB Output is correct
47 Correct 220 ms 104516 KB Output is correct
48 Correct 254 ms 104524 KB Output is correct
49 Correct 320 ms 81772 KB Output is correct
50 Correct 235 ms 81764 KB Output is correct
51 Correct 583 ms 110900 KB Output is correct
52 Correct 285 ms 110480 KB Output is correct
53 Correct 1286 ms 80104 KB Output is correct
54 Correct 494 ms 93628 KB Output is correct
55 Correct 199 ms 77760 KB Output is correct
56 Correct 374 ms 105928 KB Output is correct
57 Correct 594 ms 78376 KB Output is correct
58 Correct 851 ms 78912 KB Output is correct
59 Correct 235 ms 104504 KB Output is correct